結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
![]() |
提出日時 | 2019-02-27 00:30:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,352 bytes |
コンパイル時間 | 1,183 ms |
コンパイル使用メモリ | 110,156 KB |
実行使用メモリ | 13,756 KB |
最終ジャッジ日時 | 2024-06-23 04:57:32 |
合計ジャッジ時間 | 5,916 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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に変えたらどうなるかなども気になるところです// EPSいらないね// doubleいるね,そうだよね// それ以降で取れるやつがあるかもしれないからねint n, W;constexpr int N = 5000;vector<pair<ll, ll>> objs;ll weight_sum[N];ll value_sum[N];ll global_best;void dfs(int i, ll val, ll weight_rest) {global_best = max(global_best, val);if(i == n) return;if(weight_rest == 0) 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) <= global_best) return;// drop or adoptif(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;for(int i = 0; i < n; i++) {ll v, w;cin >> v >> w;if(w <= W) objs.emplace_back(v, w);}n = objs.size();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;}