結果
問題 | No.162 8020運動 |
ユーザー |
![]() |
提出日時 | 2020-06-01 16:37:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 578 ms / 5,000 ms |
コード長 | 1,618 bytes |
コンパイル時間 | 1,876 ms |
コンパイル使用メモリ | 169,940 KB |
実行使用メモリ | 42,496 KB |
最終ジャッジ日時 | 2024-11-21 23:18:21 |
合計ジャッジ時間 | 18,315 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<double> memo[1 << 14]; int main() { int A, N; double P[3]; cin >> A >> P[0] >> P[1] >> P[2]; N = 80 - A; for (int i = 0; i < 3; i++) { P[i] /= 100; } double dp[2][1 << 14] = {}; int now = 0, nxt = 1; dp[now][(1 << 14) - 1] = 1; auto prob = [&](int bit, int mask) { double ret = 1; for (int x = 0; x < 14; x++) { int cnt = 0; if (x != 0 && (bit & (1 << (x - 1)))) cnt++; if (x != 13 && (bit & (1 << (x + 1)))) cnt++; if (bit & (1 << x) && !(mask & (1 << x))) ret *= P[cnt]; else if (bit & (1 << x) && (mask & (1 << x))) ret *= 1 - P[cnt]; } return ret; }; for (int bit = 0; bit < (1 << 14); bit++) { for (int mask = bit; mask >= 0; mask--) { mask &= bit; memo[bit].emplace_back(prob(bit, mask)); } } while (N--) { for (int bit = 0; bit < (1 << 14); bit++) { dp[nxt][bit] = 0; } for (int bit = 0; bit < (1 << 14); bit++) { int cnt = 0; for (int mask = bit; mask >= 0; mask--) { mask &= bit; dp[nxt][mask] += dp[now][bit] * memo[bit][cnt]; cnt++; } } swap(now, nxt); } double ans = 0; for (int bit = 0; bit < (1 << 14); bit++) { ans += dp[now][bit] * __builtin_popcount(bit); } cout << fixed << setprecision(10) << ans * 2 << endl; }