QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#200392 | #2913. Archery Accuracy | JerryBlack_ZJNU | WA | 189ms | 13212kb | C++20 | 2.9kb | 2023-10-04 16:50:04 | 2023-10-04 16:50:04 |
Judging History
answer
#include <bits/stdc++.h>
#include <ctime>
//#define endl '\n'
#define ll long long //unsigned long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define PI acos(-1)
#define rep(i,n,m) for(int i=n;i<=m;i++)
#define per(i,n,m) for(int i=n;i>=m;i--)
#define bug1(i) cerr<<i<<endl
#define bug2(i,j) cerr<<i<<" "<<j<<endl
#define bug3(i,j,k) cerr<<i<<" "<<j<<" "<<k<<endl
#define bug4(i,j,k,l) cerr<<i<<" "<<j<<" "<<k<<" "<<l<<endl
#define mod 1000000007 //998244353.1000000007
#define maxn 200005
#define eps 1e-6
using namespace std;
double p[20],p1[20][20],p2[20][20];
int a[20];
double dp[30005][205];
double dpp[2][1<<18];
void solve(){
int n;
cin>>n;
rep(i,1,n) cin>>p[i];
rep(i,1,n) cin>>a[i];
rep(i,1,n){
rep(j,1,n){
int py=a[j];
double pp=p[i];
for(int x=0;x<=2*py;x++){
dp[0][x]=0;
}
dp[0][py+a[j-1]]=1;
for(int st=1;st<=3000;st++){
for(int x=0;x<=2*py;x++){
dp[st][x]=0;
if(x>=2) dp[st][x]+=dp[st-1][x-1]*pp;
if(x<=2*py-2) dp[st][x]+=dp[st-1][x+1]*(1-pp);
if(x==2*py) p1[i][j]+=dp[st][x];
}
}
for(int x=0;x<=2*py;x++){
dp[0][x]=0;
}
dp[0][py-a[j-1]]=1;
for(int st=1;st<=3000;st++){
for(int x=0;x<=2*py;x++){
dp[st][x]=0;
if(x>=2) dp[st][x]+=dp[st-1][x-1]*pp;
if(x<=2*py-2) dp[st][x]+=dp[st-1][x+1]*(1-pp);
if(x==2*py) p2[i][j]+=dp[st][x];
}
}
// cerr<<i<<" "<<j<<" "<<p1[i][j]<<" "<<p2[i][j]<<endl;
}
}
// cerr<<'a'<<endl;
dpp[0][0]=dpp[1][0]=1;
for(int st=1;st<(1<<n);st++){
int cnt=__builtin_popcount(st);
for(int j=0;j<n;j++) if(st&(1<<j)){
int pre=st^(1<<j);
dpp[0][st]=max(dpp[0][st],dpp[0][pre]*p1[j+1][cnt]+(1-dpp[0][pre])*(p2[j+1][cnt]));
dpp[0][st]=max(dpp[0][st],dpp[1][pre]*p2[j+1][cnt]+(1-dpp[1][pre])*(p1[j+1][cnt]));
dpp[1][st]=max(dpp[1][st],dpp[0][pre]*(1-p1[j+1][cnt])+(1-dpp[0][pre])*(1-p2[j+1][cnt]));
dpp[1][st]=max(dpp[1][st],dpp[1][pre]*(1-p2[j+1][cnt])+(1-dpp[1][pre])*(1-p1[j+1][cnt]));
}
}
// cout<<fixed<<setprecision(10)<<dpp[0][(1<<n)-1]<<" "<<dpp[1][(1<<n)-1]<<endl;
cout<<fixed<<setprecision(10)<<dpp[0][(1<<n)-1]<<endl;
}
/*
*/
void init(){
}
signed main(){
// #ifdef LOCAL
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
// #endif
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int ca=1;clock_t c1=clock();
init();
// cin>>ca;
while(ca--){
solve();
}
// cerr<<"Time used:"<<clock()-c1<<"ms"<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 189ms
memory: 13212kb
input:
17 0.49 0.45 0.50 0.47 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.49 0.50 0.49 0.50 0.49 15 16 17 18 19 20 26 29 86 88 89 93 95 96 97 98 100
output:
0.1083824965
result:
wrong answer 1st numbers differ - expected: '0.4516422', found: '0.1083825', error = '0.3432597'