結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
![]() |
提出日時 | 2019-02-27 00:20:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,189 bytes |
コンパイル時間 | 1,311 ms |
コンパイル使用メモリ | 109,356 KB |
実行使用メモリ | 13,764 KB |
最終ジャッジ日時 | 2024-06-23 04:57:15 |
合計ジャッジ時間 | 5,538 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 TLE * 1 -- * 17 |
ソースコード
// includes {{{ #include<iostream> #include<iomanip> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<tuple> #include<cmath> #include<random> #include<cassert> // #include<deque> // #include<multiset> // #include<bitset> // #include<cstring> // #include<bits/stdc++.h> // }}} using namespace std; using ll = long long; // こうですか.そうですよね // 0 <= z <= 1 を緩和するんですもんね // EPSの変化やDFSの探索順序,DFSをBFSに変えたらどうなるかなども気になるところです int n, W; constexpr int N = 5000; vector<pair<ll, ll>> objs; ll weight_sum[N]; ll value_sum[N]; ll global_best; constexpr double EPS = 1e-18; void dfs(int i, ll val, ll weight_rest) { global_best = max(global_best, val); if(i == n) return; int ok = i - 1, ng = n; while(ng - ok > 1) { int mid = (ng + ok) >> 1; ll sum = weight_sum[mid]; if(i - 1 >= 0) sum -= weight_sum[i - 1]; if(sum <= weight_rest) ok = mid; else ng = mid; } ll sum = 0; if(ok >= 0) sum += weight_sum[ok]; if(i - 1 >= 0) sum -= weight_sum[i - 1]; ll vsum = 0; if(ok >= 0) vsum += value_sum[ok]; if(i - 1 >= 0) vsum -= value_sum[i - 1]; double now_upper_bound = val + vsum; if(ok + 1 < n) now_upper_bound += (double) objs[ok + 1].first / objs[ok + 1].second * weight_rest; if(floor(now_upper_bound + EPS) < global_best) return; // drop or adopt if(weight_rest >= objs[i].second) dfs(i + 1, val + objs[i].first, weight_rest - objs[i].second); dfs(i + 1, val, weight_rest); } int main() { ios::sync_with_stdio(false), cin.tie(0); cin >> n >> W; objs.resize(n); for(int i = 0; i < n; i++) cin >> objs[i].first >> objs[i].second; sort(begin(objs), end(objs), [&](const pair<ll, ll> &a, const pair<ll, ll> &b) { return (double) a.first / a.second > (double) b.first / b.second; }); value_sum[0] = objs[0].first; for(int i = 1; i < n; i++) value_sum[i] = value_sum[i-1] + objs[i].first; weight_sum[0] = objs[0].second; for(int i = 1; i < n; i++) weight_sum[i] = weight_sum[i-1] + objs[i].second; dfs(0, 0, W); cout << global_best << endl; return 0; }