結果
問題 |
No.2389 Cheating Code Golf
|
ユーザー |
|
提出日時 | 2023-07-21 22:57:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 776 bytes |
コンパイル時間 | 1,941 ms |
コンパイル使用メモリ | 193,660 KB |
最終ジャッジ日時 | 2025-02-15 17:24:46 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ld = long double; int main () { int N, M; cin >> N >> M; ld A[20], B[20], P[20]; for (int i = 0; i < N; i ++) { cin >> A[i] >> B[i] >> P[i]; } ld dp[1 << 12][44]; for (auto& a : dp) { for (auto& b : a) { b = 0; } } for (int i = 1; i < (1 << N); i ++) { for (int j = 0; j <= M; j ++) { for (int k = 0; k < N; k ++) { if (!((i >> k) & 1)) { continue; } dp[i][j] = max(dp[i][j], dp[i ^ (1 << k)][j] + 1.0 / A[k]); if (j) { ld x = dp[i ^ (1 << k)][j] + 1.0 / B[k]; dp[i][j] = max(dp[i][j], dp[i][j - 1] * (1.0 - 1.0 / P[k]) + x * (1.0 / P[k])); } } if (j) dp[i][j] = max(dp[i][j], dp[i][j - 1]); } } cout << setprecision(20) << dp[(1 << N) - 1][M] << endl; }