Submission #1481614
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
const ll mod = 1e9 + 7;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;
int n, m;
long double p[105];
long double dp[105][205][105];
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> m;
rep(i, n) {cin >> p[i]; p[i] /= 100.0;}
dp[1][1][1] = 1.0;
rep2(i, 1, n)rep(j, m + 1)rep2(k, 1, n) {
if (j < k) break;
if (j == k) {
if (j + 1 > m) dp[i + 1][m][k] += dp[i][j][k] * p[i];
else dp[i + 1][j + 1][k + 1] += dp[i][j][k] * p[i];
}
else {
dp[i + 1][j][k + 1] += dp[i][j][k] * p[i];
}
if (j + 2 > m) dp[i + 1][j][k] += dp[i][j][k] * (1.0 - p[i]);
else dp[i + 1][j + 2][k + 1] += dp[i][j][k] * (1.0 - p[i]);
}
long double ans = 0.0;
rep(j, m + 1)rep(k, n + 1) ans += dp[n][j][k] * (long double)(m - k);
cout << fixed << setprecision(10) << ans << endl;
}
Submission Info
Submission Time |
|
Task |
G - 通勤電車と気分 |
User |
roto_37 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1699 Byte |
Status |
AC |
Exec Time |
20 ms |
Memory |
34432 KB |
Judge Result
Set Name |
Sample |
Subtask |
All |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
Subtask |
sample_01.txt, sample_02.txt, sample_03.txt, small_01.txt, small_02.txt, small_03.txt, small_04.txt, small_05.txt, small_06.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt |
All |
large_01.txt, large_02.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt, sample_02.txt, sample_03.txt, small_01.txt, small_02.txt, small_03.txt, small_04.txt, small_05.txt, small_06.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt |
Case Name |
Status |
Exec Time |
Memory |
large_01.txt |
AC |
14 ms |
33792 KB |
large_02.txt |
AC |
12 ms |
33664 KB |
random_01.txt |
AC |
12 ms |
33664 KB |
random_02.txt |
AC |
11 ms |
33664 KB |
random_03.txt |
AC |
8 ms |
33280 KB |
random_04.txt |
AC |
8 ms |
33152 KB |
random_05.txt |
AC |
7 ms |
33024 KB |
random_06.txt |
AC |
13 ms |
33792 KB |
random_07.txt |
AC |
14 ms |
33920 KB |
random_08.txt |
AC |
16 ms |
34176 KB |
random_09.txt |
AC |
19 ms |
34304 KB |
random_10.txt |
AC |
12 ms |
33664 KB |
random_11.txt |
AC |
12 ms |
33664 KB |
random_12.txt |
AC |
12 ms |
33664 KB |
random_13.txt |
AC |
8 ms |
33152 KB |
random_14.txt |
AC |
8 ms |
33152 KB |
random_15.txt |
AC |
8 ms |
33152 KB |
random_16.txt |
AC |
13 ms |
33920 KB |
random_17.txt |
AC |
14 ms |
33920 KB |
random_18.txt |
AC |
20 ms |
34432 KB |
random_19.txt |
AC |
19 ms |
34304 KB |
random_20.txt |
AC |
12 ms |
33664 KB |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
384 KB |
sample_03.txt |
AC |
2 ms |
2432 KB |
small_01.txt |
AC |
1 ms |
256 KB |
small_02.txt |
AC |
1 ms |
256 KB |
small_03.txt |
AC |
1 ms |
256 KB |
small_04.txt |
AC |
1 ms |
256 KB |
small_05.txt |
AC |
1 ms |
256 KB |
small_06.txt |
AC |
1 ms |
256 KB |
subtask_01.txt |
AC |
2 ms |
2432 KB |
subtask_02.txt |
AC |
2 ms |
2304 KB |
subtask_03.txt |
AC |
2 ms |
2432 KB |
subtask_04.txt |
AC |
2 ms |
2432 KB |
subtask_05.txt |
AC |
2 ms |
2432 KB |
subtask_06.txt |
AC |
2 ms |
2432 KB |
subtask_07.txt |
AC |
2 ms |
3328 KB |
subtask_08.txt |
AC |
2 ms |
2304 KB |
subtask_09.txt |
AC |
2 ms |
2304 KB |
subtask_10.txt |
AC |
2 ms |
2304 KB |
subtask_11.txt |
AC |
2 ms |
2432 KB |
subtask_12.txt |
AC |
2 ms |
2432 KB |
subtask_13.txt |
AC |
2 ms |
2432 KB |