結果
問題 | No.2158 X日後に全完するhibit君 |
ユーザー |
|
提出日時 | 2022-12-09 22:56:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 2,791 bytes |
コンパイル時間 | 1,914 ms |
コンパイル使用メモリ | 176,332 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-14 22:42:54 |
合計ジャッジ時間 | 2,877 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, K, ssum = 0, tsum = 0; cin >> n >> K; vector<array<int,3>> P(n); for(int i = 0; i < n; i++){ for(int j = 0; j < 3; j++){ cin >> P[i][j]; } ssum += P[i][1]; tsum += P[i][2]; } if(ssum <= 60){ cout << 1 << " " << 1 << " " << 1 << '\n'; return 0; } if(tsum > 60){ cout << -1 << '\n'; return 0; } vector<int> idx; for(int i = 0; i < n; i++){ int v = P[i][0] - (K + 1); for(int j = 0; j < v; j++){ idx.push_back(i); } } auto Tr = [&](int S){ int res = 0; for(int i = 0; i < idx.size(); i++){ if(S >> i & 1)res |= 1 << idx[i]; } return res; }; auto f = [&](int S){ int res = 0; for(int i = 0; i < n; i++){ if(S >> i & 1)res += P[i][1]; else res += P[i][2]; } return res; }; vector<int> dp2(1 << idx.size(), -(1 << 30)); int ans = 0; dp2[0] = K + 2; for(int i = 0; i < (1 << idx.size()); i++){ int S = 0, S2 = 0; for(int j = 0; j < idx.size(); j++){ if(i >> j & 1)continue; int p = idx[j]; if(S >> p & 1)continue; S |= 1 << p; S2 |= 1 << j; } for(int T = S2; T > 0; T = (T - 1) & S2){ if(f(Tr(T)) > 60)dp2[i | T] = max(dp2[i | T], dp2[i] + 1); } ans = max(ans, dp2[i]); } double ans2 = K + 2; vector<double> dp(1 << idx.size()); dp[0] = 1; for(int i = 0; i < (1 << idx.size()); i++){ if(dp[i] == 0)continue; int S = 0, S2 = 0; for(int j = 0; j < idx.size(); j++){ if(i >> j & 1)continue; int p = idx[j]; if(S >> p & 1)continue; S |= 1 << p; S2 |= 1 << j; } auto f2 = [&](int S3){ vector<int> rem(n); for(int j = 0; j < idx.size(); j++){ if(~i >> j & 1)rem[idx[j]]++; } double res = 1; int S4 = Tr(S3); for(int j = 0; j < n; j++){ int b = P[j][0] - K; if(S4 >> j & 1) res *= double(rem[j]) / b; else res *= double(b - rem[j]) / b; } return res; }; for(int T = S2; T > 0; T = (T - 1) & S2){ if(f(Tr(T)) > 60){ auto p = f2(T); dp[i | T] += dp[i] * p; ans2 += dp[i] * p; } } } cout << fixed << setprecision(15); cout << K + 2 << " " << ans << " " << ans2 << '\n'; }