結果

問題 No.626 Randomized 01 Knapsack
ユーザー lumc_
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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に変えたらどうなるかなども気になるところです

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