QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#282414 | #3247. 挑战 | kilo_tobo_tarjen# | AC ✓ | 518ms | 22572kb | C++20 | 1.6kb | 2023-12-11 23:13:02 | 2023-12-11 23:13:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long double lf;
const int maxn=1e5+10;
lf dp[3][maxn];//我有 我有extra 他有 now
int p[maxn],q[maxn];
int n;
pair<lf,lf> solve(int x,int y){
lf all=(lf)x*(y+1);
int t=min(x,y);
lf g=(lf)(1+t)*t;
g/=2.;
if(x>t)g+=(lf)(x-t)*(y+1);
lf T=(lf)t;
// cout<<x<<" "<<y<<"\n";
// cout<<g/all<<" "<<T/all<<"\n";
return make_pair(g/all,T/all);
}
lf dfs(int i,int x){
if(dp[i][x]>-0.5)return dp[i][x];
if(p[x]+x>=n)return dp[i][x]=1.;
if(i==0){
lf g=1.;
for(int j=1;j<=p[x];j++)g=min(g,dfs(1,x+j));
return dp[i][x]=1.-g;
}
if(i==2){
lf g=0;
for(int j=1;j<=p[x];j++)g=max(g,dfs(1,x+j));
return dp[i][x]=g;
}
if(i==1){
lf g=1.;
for(int j=1;j<=p[x];j++){
g=min(g,dfs(1,x+j));
}
for(int j=1;j<p[x];j++){
auto [p1,p2]=solve(p[x]-j,q[x]+q[x+j]);
lf p3=1.-p1-p2;
g=min(g,p1*(1.-dfs(0,x+j))+p2*dfs(1,x+j)+p3*dfs(2,x+j));
}
return dp[i][x]=1.-g;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(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=0;i<3;i++){
for(int t=0;t<n;t++)dp[i][t]=-1.;
}
cout<<fixed<<setprecision(10)<<dfs(1,0)<<"\n";
// for(int i=0;i<3;i++){
// for(int t=0;t<n;t++)if(dp[i][t]>-0.5){
// cout<<"dp["<<i<<"]["<<t<<"]="<<dfs(i,t)<<"\n";
// }
// }
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 7928kb
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: 10ms
memory: 22572kb
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: 518ms
memory: 22408kb
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: 1ms
memory: 6048kb
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: 2ms
memory: 8072kb
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: 2ms
memory: 8080kb
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: 111ms
memory: 22548kb
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: 109ms
memory: 22444kb
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: 82ms
memory: 22344kb
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: 67ms
memory: 22564kb
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: 11ms
memory: 22404kb
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'