結果

問題 No.626 Randomized 01 Knapsack
ユーザー lumc_lumc_
提出日時 2019-02-27 00:28:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,170 bytes
コンパイル時間 994 ms
コンパイル使用メモリ 110,196 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-23 04:57:26
合計ジャッジ時間 1,664 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 9 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// 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
// EPSDFSDFSBFS
// 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];
ll now_upper_bound = val + vsum;
if(now_upper_bound <= 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;
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0