QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #563129 | #3247. 挑战 | Elegia | AC ✓ | 172ms | 12308kb | C++23 | 1.2kb | 2024-09-14 02:59:51 | 2024-09-14 02:59:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
double coef[335][667][3] , prob[100003][3]; int p[100003] , q[100003] , N;
int main(){
ios::sync_with_stdio(0); cin >> N;
for(int i = 0 ; i < N ; ++i) cin >> p[i];
for(int i = 0 ; i < N ; ++i) cin >> q[i];
for(int i = 1 ; i <= 333 ; ++i)
for(int j = 1 ; j <= 666 ; ++j){
int win = 0 , eq = 0 , lose = 0; for(int k = 1 ; k <= i ; ++k){win += min(j + 1 , k); eq += k <= j; lose += max(0 , j - k);}
int sum = i * (1 + j); coef[i][j][0] = 1.0 * win / sum; coef[i][j][1] = 1.0 * eq / sum; coef[i][j][2] = 1.0 * lose / sum;
}
prob[N][0] = prob[N][1] = prob[N][2] = 1;
for(int i = N - 1 ; ~i ; --i){
for(int j = 1 ; j + i <= N && j <= p[i] ; ++j){
prob[i][1] = max(prob[i][1] , (i + j == N ? 1 : 1 - prob[i + j][0])); prob[i][2] = max(prob[i][2] , prob[i + j][0]);
if(p[i] > j && j + i < N){
int coefp = p[i] - j , coefq = q[i] + q[i + j];
prob[i][0] = max(prob[i][0] , coef[coefp][coefq][0] * prob[i + j][1] + coef[coefp][coefq][1] * (1 - prob[i + j][0]) + coef[coefp][coefq][2] * (1 - prob[i + j][2]));
}
prob[i][0] = max(prob[i][0] , prob[i][1]);
}
}
cout << fixed << setprecision(10) << prob[0][0] << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 35ms
memory: 11884kb
input:
1000 5 1 33 33 35 2 28 10 2 24 12 19 30 32 3 23 27 3 35 15 13 24 27 13 5 25 3 27 16 18 35 17 11 6 22 1 30 12 11 25 12 17 15 6 17 5 4 25 5 26 2 23 7 18 21 18 31 24 1 15 29 15 16 33 28 23 24 12 13 26 25 28 2 9 27 2 25 16 27 5 20 17 4 4 35 17 17 24 2 27 35 28 3 15 33 33 7 9 6 2 9 34 29 10 27 15 16 32 2...
output:
0.9251428145
result:
ok found '0.9251428', expected '0.9251428', error '0.0000000'
Test #2:
score: 0
Accepted
time: 47ms
memory: 12188kb
input:
99998 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #3:
score: 0
Accepted
time: 172ms
memory: 12252kb
input:
100000 333 333 333 333 333 332 331 333 332 331 331 332 331 332 333 331 333 331 332 330 330 333 332 333 331 333 332 330 330 333 332 330 330 333 331 331 333 331 331 333 331 331 330 332 331 333 332 332 332 330 333 330 332 332 333 330 331 332 332 331 332 331 331 330 330 332 333 333 333 331 330 330 333 3...
output:
0.5000000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 36ms
memory: 9136kb
input:
1000 13 28 2 41 9 33 40 44 13 23 39 40 18 20 11 13 32 22 22 9 11 29 43 4 20 31 2 13 19 23 35 3 9 25 36 22 9 6 15 12 41 41 44 15 30 28 19 10 39 19 32 10 39 31 3 13 27 33 31 16 2 1 20 42 17 8 16 21 13 26 16 29 20 21 10 2 12 44 36 30 25 27 38 42 27 36 34 26 9 19 1 40 41 21 11 33 15 23 10 31 24 31 33 4 ...
output:
0.8778247505
result:
ok found '0.8778248', expected '0.8778248', error '0.0000000'
Test #5:
score: 0
Accepted
time: 39ms
memory: 11784kb
input:
1000 46 69 32 80 20 9 30 55 31 28 75 61 9 83 3 28 47 20 37 51 23 49 38 43 59 50 63 33 54 45 61 20 44 84 38 33 88 6 88 25 80 26 53 49 44 16 55 68 80 2 40 5 34 42 38 10 44 35 8 5 90 80 8 27 8 81 73 20 74 74 36 21 78 47 10 19 52 12 45 61 75 51 23 10 7 71 55 71 39 52 18 36 11 78 59 76 87 23 44 54 45 36 ...
output:
0.9030077939
result:
ok found '0.9030078', expected '0.9030078', error '0.0000000'
Test #6:
score: 0
Accepted
time: 39ms
memory: 11616kb
input:
1000 11 2 14 11 26 36 36 18 27 36 32 9 30 6 10 8 10 24 18 7 13 14 32 6 1 37 8 16 18 23 8 30 2 4 17 37 39 32 28 27 30 14 5 24 30 30 35 12 20 33 30 2 6 31 38 10 3 36 17 11 36 30 7 20 19 30 25 39 39 35 17 7 7 12 35 1 24 25 38 10 31 24 38 3 38 18 12 36 38 18 20 33 17 4 18 24 4 27 37 12 17 16 6 23 17 17 ...
output:
0.8969355546
result:
ok found '0.8969356', expected '0.8969356', error '0.0000000'
Test #7:
score: 0
Accepted
time: 69ms
memory: 12156kb
input:
100000 3 6 6 333 2 3 3 100 100 333 1 5 2 4 100 2 4 5 1 3 100 333 6 5 6 333 100 1 1 2 4 100 3 3 333 5 3 4 3 100 4 333 1 4 2 6 6 6 6 100 5 5 5 3 333 2 1 3 333 3 3 3 2 2 100 5 4 2 2 100 1 3 2 100 5 6 2 5 2 2 3 5 1 4 2 3 6 2 5 6 333 333 2 4 4 6 4 3 100 333 1 2 2 100 333 4 6 3 4 6 1 100 100 4 6 100 5 2 6...
output:
0.0093483205
result:
ok found '0.0093483', expected '0.0093483', error '0.0000000'
Test #8:
score: 0
Accepted
time: 71ms
memory: 12256kb
input:
100000 3 100 4 3 5 5 5 333 2 5 2 2 2 2 2 4 2 333 5 3 3 5 333 1 100 2 2 5 100 333 5 1 3 3 2 333 4 5 4 5 1 333 333 333 1 100 2 4 333 1 2 1 4 100 4 3 5 1 2 2 3 5 3 4 1 4 100 3 2 333 5 5 4 2 100 3 2 5 100 100 4 1 3 333 3 333 100 1 1 1 100 100 1 333 5 4 100 5 2 5 5 4 100 3 1 100 4 333 100 333 2 4 5 333 2...
output:
0.0061677166
result:
ok found '0.0061677', expected '0.0061677', error '0.0000000'
Test #9:
score: 0
Accepted
time: 68ms
memory: 12304kb
input:
100000 1 1 5 6 333 6 100 7 3 5 333 1 1 6 2 100 7 7 6 100 6 100 100 2 1 4 5 333 333 4 2 4 4 100 6 2 7 7 6 333 6 333 1 4 4 4 3 2 100 2 5 7 6 1 2 3 5 2 100 5 7 1 6 5 1 3 1 333 5 1 6 333 2 1 333 3 333 1 1 2 6 5 3 3 1 2 333 3 2 7 4 2 6 6 1 1 5 100 5 3 5 100 333 1 7 7 333 1 1 5 6 3 1 100 5 100 7 1 7 6 4 5...
output:
0.0133352716
result:
ok found '0.0133353', expected '0.0133353', error '0.0000000'
Test #10:
score: 0
Accepted
time: 62ms
memory: 12264kb
input:
100000 5 8 6 14 12 6 2 12 13 14 5 14 10 10 3 5 5 11 100 10 14 8 333 333 100 5 12 333 14 3 7 3 12 7 2 14 12 11 13 6 11 100 333 6 9 2 14 1 14 6 100 14 5 1 6 4 100 1 5 1 9 4 12 6 3 6 12 11 8 12 11 3 6 11 9 3 13 9 2 3 333 12 9 100 100 5 8 8 2 8 1 3 4 14 100 100 12 9 100 9 8 7 3 9 10 10 7 333 333 2 8 2 1...
output:
0.4698750771
result:
ok found '0.4698751', expected '0.4698751', error '0.0000000'
Test #11:
score: 0
Accepted
time: 47ms
memory: 12308kb
input:
99999 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'