QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#597615 | #3247. 挑战 | ccpy | AC ✓ | 499ms | 40904kb | C++20 | 1.3kb | 2024-09-28 18:10:48 | 2024-09-28 18:10:53 |
Judging History
answer
#include<bits/stdc++.h>
#define MAX 100005
using namespace std;
int n,p[MAX],q[MAX];
#define db long double
db f[1005][1005],g[1005][1005];
db h[MAX][3];
void sol(){
cin>>n;
for(int i=0;i<n;i++) cin>>p[i];
for(int i=0;i<n;i++) cin>>q[i];
h[n][0]=h[n][1]=h[n][2]=0;
for(int i=n-1;~i;i--){
for(int j=1;j<=p[i]&&i+j<=n;j++){
h[i][0]=max(h[i][0],1-h[i+j][1]);
h[i][1]=max(h[i][1],1-h[i+j][1]);
h[i][2]=max(h[i][2],h[i+j][1]);
if(j!=p[i]){
db wn=f[p[i]-j][q[i]+q[i+j]];
db ls=1-wn-g[p[i]-j][q[i]+q[i+j]];
db rt=wn*h[i+j][0]+(1-wn-ls)*(1-h[i+j][1])+ls*(1-h[i+j][2]);
//cout<<"i="<<i<<" "<<j<<" "<<wn<<" "<<ls<<endl;
h[i][1]=max(h[i][1],rt);
}
}
//cout<<h[i][0]<<" "<<h[i][1]<<" "<<h[i][2]<<endl;
}
cout<<setprecision(18)<<h[0][1];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
for(int i=1;i<=1000;i++){
for(int j=1;j<=1000;j++){
f[i][j]=f[i-1][j]*(i-1)/i;
if(j<i) f[i][j]+=1.0/i;
else f[i][j]+=1.0/(j+1);
g[i][j]=g[i-1][j]*(i-1)/i;
if(j>=i) g[i][j]+=1.0/(j+1)/i;
}
}
while(t--) sol();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 35324kb
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.925142814479831732
result:
ok found '0.9251428', expected '0.9251428', error '0.0000000'
Test #2:
score: 0
Accepted
time: 14ms
memory: 40796kb
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
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #3:
score: 0
Accepted
time: 499ms
memory: 40800kb
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.5
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 6ms
memory: 35200kb
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.877824750544605277
result:
ok found '0.8778248', expected '0.8778248', error '0.0000000'
Test #5:
score: 0
Accepted
time: 5ms
memory: 35260kb
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.903007793854057676
result:
ok found '0.9030078', expected '0.9030078', error '0.0000000'
Test #6:
score: 0
Accepted
time: 6ms
memory: 35340kb
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.896935554594115579
result:
ok found '0.8969356', expected '0.8969356', error '0.0000000'
Test #7:
score: 0
Accepted
time: 87ms
memory: 40740kb
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.00934832052641643092
result:
ok found '0.0093483', expected '0.0093483', error '0.0000000'
Test #8:
score: 0
Accepted
time: 105ms
memory: 40904kb
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.00616771657079922554
result:
ok found '0.0061677', expected '0.0061677', error '0.0000000'
Test #9:
score: 0
Accepted
time: 88ms
memory: 40748kb
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.0133352716246820585
result:
ok found '0.0133353', expected '0.0133353', error '0.0000000'
Test #10:
score: 0
Accepted
time: 63ms
memory: 40756kb
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.469875077077288322
result:
ok found '0.4698751', expected '0.4698751', error '0.0000000'
Test #11:
score: 0
Accepted
time: 7ms
memory: 40684kb
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
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'