結果

問題 No.626 Randomized 01 Knapsack
ユーザー lumc_lumc_
提出日時 2019-02-27 04:13:29
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 2,544 bytes
コンパイル時間 955 ms
コンパイル使用メモリ 107,848 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-05 09:06:50
合計ジャッジ時間 2,019 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 3 ms
4,376 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 3 ms
4,376 KB
testcase_12 AC 4 ms
4,376 KB
testcase_13 AC 3 ms
4,376 KB
testcase_14 AC 3 ms
4,376 KB
testcase_15 AC 4 ms
4,380 KB
testcase_16 AC 4 ms
4,380 KB
testcase_17 AC 4 ms
4,376 KB
testcase_18 AC 4 ms
4,376 KB
testcase_19 AC 4 ms
4,380 KB
testcase_20 AC 5 ms
4,376 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 4 ms
4,376 KB
testcase_23 AC 5 ms
4,376 KB
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];

  global_best = max(global_best, val + vsum); // 実行可能

  double now_upper_bound = val + vsum;
  if(ok + 1 < n) now_upper_bound += (double) objs[ok + 1].first / objs[ok + 1].second * (weight_rest - sum);

  if(floor(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