QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #203218 | #3994. Easy Jump | zswzswzsw | WA | 0ms | 4292kb | C++14 | 2.0kb | 2023-10-06 16:10:21 | 2023-10-06 16:10:22 |
Judging History
answer
#include<bits/stdc++.h>
#define MAXN 500010
using namespace std;
int n, mH, mS, K, T1, T2;
double dp[1010][12][12], P[MAXN];
bool vis[1010][12][12], mark[1010];
double DFS(int i, int H, int S) {
if(i==n+1)return 0;
if (vis[i][H][S])return dp[i][H][S];
vis[i][H][S] = true;
if (T1 < T2) {
if (mark[i]) {
double tmp = P[i];
for (int j = 1; j <= H - 2; j++) {
dp[i][H][S] += 1.0 * (0.0 + DFS(i + 1, H - j + 1, mS) + j) * tmp;
tmp = tmp * (1.0 - P[i]);
}
tmp = pow(1.0 - P[i], H - 2);
dp[i][H][S]+=(DFS(i+1,2,mS)+(P[i]+(1.0-P[i])*(T1+1))/P[i]+H-2)*tmp;
if(H<mH)dp[i][H][S]=min(dp[i][H][S],DFS(i,H+1,mS)+T1);
//dp[i][H][S] += (DFS(i + 1, 2, mS) * P[i] + 1.0 * T1 * (1.0 - P[i]) + 1) / (1.0 / tmp - (1.0 - P[i]));
} else {
double tmp = P[i];
for (int j = 1; j <= H - 2 + S; j++) {
if (H - j + 1 >= 2)dp[i][H][S] += 1.0 * (0.0 + DFS(i + 1, H - j + 1, S) + j) * tmp;
else {
int sh = j - 1 - (H - 2);
dp[i][H][S] += 1.0 * (0.0 + DFS(i + 1, 2, S - sh) + j + sh * T1) * tmp;
}
tmp = tmp * (1.0 - P[i]);
}
tmp = pow((1.0 - P[i]), H - 2 + S);
dp[i][H][S]+=(DFS(i+1,2,0)+(P[i]+(1.0-P[i])*(T2+1))/P[i]+H-2+(T1+1)*S)*tmp;
//dp[i][H][S] += (DFS(i + 1, 2, 0) * P[i] + 1.0 * T2 * (1.0 - P[i]) + 1) / (1.0 / tmp - (1.0 - P[i]));
}
} else {
double tmp = P[i];
for (int j = 1; j <= H - 2; j++) {
dp[i][H][S] += 1.0 * (0.0 + DFS(i + 1, H - j + 1, mS) + j) * tmp;
tmp = tmp * (1.0 - P[i]);
}
tmp = pow(1.0 - P[i], H - 2);
dp[i][H][S]+=(DFS(i+1,2,S)+(P[i]+(1.0-P[i])*(T2+1))/P[i]+H-2)*tmp;
//dp[i][H][S] += (DFS(i + 1, 2, S) * P[i] + 1.0 * T2 * (1.0 - P[i]) + 1) / (1.0 / tmp - (1.0 - P[i]));
}
return dp[i][H][S];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> mH >> mS;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
P[i] = 1.0 * x / 100;
}
cin >> K;
for (int i = 1; i <= K; i++) {
int x;
cin >> x;
mark[x] = true;
}
cin >> T1 >> T2;
printf("%.10f",DFS(1,mH,mS));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4032kb
input:
1 2 0 50 0 1 2
output:
4.0000000000
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4260kb
input:
2 3 1 50 50 1 1 1 3
output:
6.0000000000
result:
ok found '6.0000000', expected '6.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4124kb
input:
1 6 4 75 0 64 6
output:
1.3411458333
result:
ok found '1.3411458', expected '1.3411458', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4064kb
input:
1 5 1 61 1 1 15 43
output:
2.2082231967
result:
ok found '2.2082232', expected '2.2082232', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4292kb
input:
10 9 3 12 65 76 33 17 20 89 16 4 63 3 2 4 8 73 21
output:
942.4148420128
result:
ok found '942.4148420', expected '942.4148420', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
10 6 0 26 6 29 76 92 46 8 4 91 44 1 4 17 6
output:
401.8668629820
result:
ok found '401.8668630', expected '401.8668630', error '0.0000000'
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 4272kb
input:
100 3 5 85 59 20 75 58 42 79 95 22 15 95 81 69 73 45 42 99 93 58 8 18 34 88 14 23 37 87 16 96 17 40 58 32 26 93 9 37 15 68 49 99 73 48 79 16 27 52 4 66 53 48 55 27 56 52 66 25 30 34 11 97 20 38 30 4 78 17 98 4 23 30 71 87 94 89 71 45 92 72 24 90 24 78 48 62 82 30 30 27 55 64 66 41 72 53 97 59 38 80 ...
output:
13518.2586150137
result:
wrong answer 1st numbers differ - expected: '13395.8550625', found: '13518.2586150', error = '0.0091374'