結果
| 問題 | No.1151 チャレンジゲーム |
| ユーザー |
 沙耶花
|
| 提出日時 | 2020-08-07 22:41:48 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 1,550 bytes |
| コンパイル時間 | 2,382 ms |
| コンパイル使用メモリ | 218,164 KB |
| 実行使用メモリ | 816,640 KB |
| 最終ジャッジ日時 | 2024-09-24 22:56:22 |
| 合計ジャッジ時間 | 5,332 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 17 ms
14,848 KB |
| testcase_01 | AC | 56 ms
41,472 KB |
| testcase_02 | AC | 107 ms
76,928 KB |
| testcase_03 | AC | 12 ms
10,368 KB |
| testcase_04 | AC | 11 ms
10,624 KB |
| testcase_05 | AC | 19 ms
14,976 KB |
| testcase_06 | AC | 18 ms
14,848 KB |
| testcase_07 | AC | 31 ms
23,680 KB |
| testcase_08 | AC | 30 ms
23,936 KB |
| testcase_09 | AC | 55 ms
41,472 KB |
| testcase_10 | AC | 56 ms
41,472 KB |
| testcase_11 | AC | 107 ms
76,928 KB |
| testcase_12 | AC | 109 ms
76,800 KB |
| testcase_13 | MLE | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000001
int N;
vector<int> A;
vector<vector<double>> P;
int t= 0;
double get(int state,int s,int t,int now){
if(state==(1<<N)-1){
if(s>t)return 1.0;
else return 0.0;
}
static vector dp(1<<N,vector(201,vector(201,vector<double>(2,-100.0))));
if(dp[state][s][t][now]>-1.0)return dp[state][s][t][now];
double ret;
if(now==0)ret = 0.0;
else ret = 1.0;
int ind = 0;
for(int i=0;i<N;i++){
if((state>>i)&1)continue;
double m;
if(now==0)m=1.0;
else m = 0.0;
for(int j=0;j<N;j++){
if((state>>j)&1)continue;
double p = P[i][j];
if(now==0){
m = min(m,get(state|(1<<i),s+A[i],t,1)*p + get(state|(1<<j),s,t+A[j],0)*(1.0-p));
}
else{
m = max(m,get(state|(1<<i),s,t+A[i],0)*p + get(state|(1<<j),s+A[j],t,1)*(1.0-p));
}
}
//cout<<state<<','<<now<<','<<m<<endl;
if(now==0)ret = max(ret,m);
else ret = min(ret,m);
}
dp[state][s][t][now] = ret;
return ret;
}
int main(){
cin>>N;
A.resize(N);
for(int i=0;i<N;i++)cin>>A[i];
P.resize(N,vector<double>(N,0.0));
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(A[i]==1){
P[i][j]=1.0;
continue;
}
if(A[j]==1){
P[i][j]=1.0/A[i];
continue;
}
for(int k=1;k<=1000;k+=2){
P[i][j] += pow(1.0/(double)A[i],1) * pow(1.0-(1.0/(double)A[i]),k/2) * pow(1.0-(1.0/(double)A[j]),k/2);
}
}
}
//cout<<'a'<<endl;
cout<<fixed<<setprecision(10)<<get(0,0,0,0)<<endl;
return 0;
}