結果
問題 | No.2158 X日後に全完するhibit君 |
ユーザー |
![]() |
提出日時 | 2022-12-09 22:55:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 4,485 bytes |
コンパイル時間 | 1,348 ms |
コンパイル使用メモリ | 124,644 KB |
最終ジャッジ日時 | 2025-02-09 08:40:59 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <vector>#include <queue>#include <deque>#include <set>#include <map>#include <tuple>#include <cmath>#include <numeric>#include <functional>#include <cassert>#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }using namespace std;typedef long long ll;template<typename T>vector<vector<T>> vec2d(int n, int m, T v){return vector<vector<T>>(n, vector<T>(m, v));}template<typename T>vector<vector<vector<T>>> vec3d(int n, int m, int k, T v){return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, v)));}template<typename T>void print_vector(vector<T> v, char delimiter=' '){if(v.empty()) {cout << endl;return;}for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter;cout << v.back() << endl;}const int MX = 60;int main(){ios::sync_with_stdio(false);cin.tie(0);cout << setprecision(10) << fixed;int n, k; cin >> n >> k;vector<int> p(n), S(n), T(n);for(int i = 0; i < n; i++) cin >> p[i] >> S[i] >> T[i];int s_sum = accumulate(S.begin(), S.end(), 0);int t_sum = accumulate(T.begin(), T.end(), 0);if(t_sum > MX){cout << -1 << endl;return 0;}if(s_sum <= MX){cout << 1 << ' ' << 1 << ' ' << 1 << endl;return 0;}vector<int> prod(n);for(int i = 0; i < n; i++){prod[i] = 1;for(int j = i+1; j < n; j++){prod[i] *= p[j];}}auto to_int = [&](vector<int> &v){int ans = 0;for(int i = 0; i < n; i++){ans += prod[i]*v[i];}return ans;};auto to_vec = [&](int s){vector<int> ans(n);for(int i = 0; i < n; i++){ans[i] = s/prod[i];s %= prod[i];}return ans;};vector<int> x = {2, 1};auto v = vector<int>(n);for(int i = 0; i < n; i++) v[i] = p[i]-1;int s_max = to_int(v);int goal = s_max+1;vector<int> mn(s_max+2, 1e9);vector<int> mx(s_max+2, 0);vector<double> pr(s_max+2);vector<double> e(s_max+2);vector<bool> ok(s_max+2);ok[s_max] = true;mn[s_max] = 1;mx[s_max] = 1;pr[s_max] = 1;e[s_max] = 1;for(int s = 0; s <= s_max; s++){auto v = to_vec(s);}for(int s = s_max; s >= 0; s--){if(!ok[s]) continue;// debug_value(s)auto v = to_vec(s);// print_vector(v);// int mask = 0;// for(int i = 0; i < n; i++){// if(v[i] > 0) mask += 1<<i;// }for(int t = 0; t < (1<<n); t++){// if((t|mask) > mask) continue;double proba = 1.0;for(int i = 0; i < n; i++){int already = p[i]-v[i];int already_and_ok = already > k ? already-k : 0;int ok = already_and_ok+v[i];if(t&(1<<i)){proba *= (double)v[i]/(double)ok;}else{proba *= (double)(already_and_ok)/(double)ok;}}if(proba == 0.0) continue;auto u = v;int total_time = 0;for(int i = 0; i < n; i++){if(t&(1<<i)) { // 新たな問題u[i]--;total_time += S[i];}else{total_time += T[i];}}// print_vector(u);int s_nx = to_int(u);if(total_time <= MX){chmax(mx[goal], mx[s]+1);chmin(mn[goal], mn[s]+1);e[goal] += (e[s]+pr[s])*proba;ok[goal] = true;}else{pr[s_nx] += pr[s]*proba;e[s_nx] += (e[s]+pr[s])*proba;chmax(mx[s_nx], mx[s]+1);chmin(mn[s_nx], mn[s]+1);ok[s_nx] = true;}}}// debug_value(mn[0])// debug_value(ok[goal])cout << mn[goal] << ' ' << mx[goal] << ' ' << e[goal] << endl;}