QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#200421#2913. Archery AccuracyJerryBlack_ZJNUTL 0ms0kbC++233.1kb2023-10-04 16:56:212023-10-04 16:56:22

Judging History

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

  • [2023-10-04 16:56:22]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-10-04 16:56:21]
  • 提交

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[67005][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<=67000;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<=67000;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;
}


/*
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
*/
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
Time Limit Exceeded

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:


result: