QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#693052 | #9162. COVID tests | RDFZchenyy | 0 | 623ms | 23608kb | C++14 | 976b | 2024-10-31 15:26:17 | 2024-10-31 15:26:36 |
Judging History
answer
#include<bits/stdc++.h>
using ld=long double;
#define MAXN 1005
int n; ld p;
ld f[MAXN][MAXN],g[MAXN];
int pf[MAXN][MAXN],pg[MAXN];
ld pl[MAXN];
ld fpow(ld a,int b){
ld res=1; for(;b;b>>=1,a*=a) if(b&1) res*=a;
return res;
}
int main(){
std::cin>>n>>p;
f[0][0]=0,g[0]=0;
for(int i=1;i<=n;i++){
pl[i]=(1.0-fpow(1.0-p,i));
}
for(int i=1;i<=n;i++){
pf[i][1]=0,f[i][1]=g[i-1];
for(int j=2;j<=i;j++){
pf[i][j]=-1,f[i][j]=1e18;
for(int x=1;x<j;x++){
ld pn=pl[x]/pl[j];
ld val=1+f[i][x]*pn+f[i-x][j-x]*(1-pn);
if(val<=f[i][j]) f[i][j]=val,pf[i][j]=x;
}
}
g[i]=1e18; pg[i]=-1;
for(int x=1;x<=i;x++){
ld pn=pl[x];
ld val=1+pn*f[i][x]+(1.0-pn)*g[i-x];
if(val<g[i]) g[i]=val,pg[i]=x;
}
}
std::cout<<g[n]<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 496ms
memory: 23408kb
input:
1000 0.789673 1
output:
1000
result:
wrong answer doesn't correspond to pattern "(Q)|(A)"
Subtask #2:
score: 0
Wrong Answer
Test #18:
score: 0
Wrong Answer
time: 623ms
memory: 23608kb
input:
1000 0.001 300
output:
11.6472
result:
wrong answer 2" doesn't correspond to pattern "(Q)|(A)"