QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#597615#3247. 挑战ccpyAC ✓499ms40904kbC++201.3kb2024-09-28 18:10:482024-09-28 18:10:53

Judging History

This is the latest submission verdict.

  • [2024-09-28 18:10:53]
  • Judged
  • Verdict: AC
  • Time: 499ms
  • Memory: 40904kb
  • [2024-09-28 18:10:48]
  • Submitted

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();
}

詳細信息

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'