結果
問題 | No.1590 Random Shopping |
ユーザー |
![]() |
提出日時 | 2021-07-09 05:20:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 842 ms / 5,000 ms |
コード長 | 980 bytes |
コンパイル時間 | 716 ms |
コンパイル使用メモリ | 89,024 KB |
最終ジャッジ日時 | 2025-01-22 20:00:07 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <iostream> #include <cmath> #include <algorithm> using namespace std; typedef long double ld; int a[1010]; ld r[1010],dp[510][510] = {}; int main(){ cout.precision(20); int i,j,k,n; cin >> n; for(i=0;i<n;i++) cin >> a[i]; for(i=0;i<n;i++) cin >> r[i]; ld ans = 0; for(int val = 1;val<=1000;val++){ for(i=0;i<=n;i++){ for(j=0;j<=n + 1;j++) dp[i][j] = 0; } dp[0][0] = 1; for(i=1;i<=n;i++){ for(j=0;j<=i;j++){ if(a[i - 1]<val){ dp[i][j] = dp[i - 1][j]/2; if(j>0) dp[i][j] += dp[i - 1][j - 1]/2; }else{ if(j>0) dp[i][j] = dp[i - 1][j]/2 + dp[i - 1][j + 1]/2; else dp[i][j] = dp[i - 1][j] + dp[i - 1][j + 1]/2; } } } for(i=1;i<=n;i++){ if(a[i - 1]>=val) ans += r[i - 1]*dp[i - 1][0]/2; } } cout << ans << endl; }