QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#282414#3247. 挑战kilo_tobo_tarjen#AC ✓518ms22572kbC++201.6kb2023-12-11 23:13:022023-12-11 23:13:02

Judging History

你现在查看的是最新测评结果

  • [2023-12-11 23:13:02]
  • 评测
  • 测评结果:AC
  • 用时:518ms
  • 内存:22572kb
  • [2023-12-11 23:13:02]
  • 提交

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'