結果

問題 No.626 Randomized 01 Knapsack
ユーザー lumc_lumc_
提出日時 2019-02-27 00:28:50
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,170 bytes
コンパイル時間 941 ms
コンパイル使用メモリ 108,716 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-05 09:04:49
合計ジャッジ時間 2,242 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 WA -
testcase_02 AC 2 ms
4,376 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 2 ms
4,380 KB
testcase_06 WA -
testcase_07 AC 2 ms
4,376 KB
testcase_08 WA -
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 3 ms
4,380 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 4 ms
4,376 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 3 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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 を緩和するんですもんね
// 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];

  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;
}
0