結果
問題 |
No.2389 Cheating Code Golf
|
ユーザー |
|
提出日時 | 2023-07-21 21:47:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 620 bytes |
コンパイル時間 | 560 ms |
コンパイル使用メモリ | 70,912 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-21 23:15:07 |
合計ジャッジ時間 | 2,158 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include<iostream> #include<iomanip> #include<cassert> using namespace std; int N,M; int A[12],B[12],P[12]; double dp[1<<12][41]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N>>M; for(int i=0;i<N;i++)cin>>A[i]>>B[i]>>P[i]; for(int i=0;i<1<<N;i++)for(int j=0;j<=M;j++) { double ans=0; for(int k=0;k<N;k++)if(i>>k&1) { double prob=1; double cur=0; for(int t=0;t<=j;t++) { ans=max(ans,cur+(dp[i^1<<k][j-t]+1./A[k])*prob); cur+=(dp[i^1<<k][j-t]+1./B[k])*prob/P[k]; prob*=1-1./P[k]; } } dp[i][j]=ans; } cout<<fixed<<setprecision(16)<<dp[(1<<N)-1][M]<<endl; }