結果

問題 No.2364 Knapsack Problem
ユーザー KoseTKoseT
提出日時 2023-07-01 19:39:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,933 bytes
コンパイル時間 2,168 ms
コンパイル使用メモリ 210,716 KB
実行使用メモリ 4,968 KB
最終ジャッジ日時 2023-09-22 13:51:28
合計ジャッジ時間 3,167 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
 
using namespace std;

void print_bit(int num) {
  for (int i=0;i<18;++i) {
    if (num & (1<<i)) cout << '1';
    else cout << '0';
  }
  cout << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, w;
  cin >> n >> m >> w;
  vector<pair<int, long>> merch(n), magic(m);
  for (int i=0;i<n;++i) cin >> merch[i].first;
  for (int i=0;i<n;++i) cin >> merch[i].second;
  for (int i=0;i<n;++i) cin >> magic[i].first;
  for (int i=0;i<n;++i) cin >> magic[i].second;

  vector<vector<int>> is_used(1<<(n+m), vector<int>(n+m, -1)); // weights
  queue<pair<int, int>> que;
  for (int i=0;i<n;++i) {
    if (w < merch[i].first) continue;
    que.push(make_pair(1<<i, i));
    is_used[1<<i][i] = merch[i].first;
  }
  while (!que.empty()) {
    pair<int, int> ct = que.front(); que.pop();
    int now_w {is_used[ct.first][ct.second]};
    for (int i=0;i<n;++i) {
      if (is_used[ct.first|(1<<i)][i] != -1) continue;
      int next_w {is_used[ct.first][ct.second] + merch[i].first};
      if (next_w <= w) {
        is_used[ct.first|(1<<i)][i] = next_w;
        que.push(make_pair(ct.first|(1<<i), i));
      }
    }
    for (int i=0;i<m;++i) {
      if (is_used[ct.first|(1<<(i+n))][i+n] != -1) continue;
      int next_w {is_used[ct.first][ct.second] - magic[i].first};
      if (0 <= next_w) {
        is_used[ct.first|(1<<(i+n))][i+n] = next_w;
        que.push(make_pair(ct.first|(1<<(i+n)), i+n));
      }
    }
  }
  long long ans {};
  for (int i=0;i<(1<<(n+m));++i) {
    int acc = accumulate(is_used[i].begin(), is_used[i].end(), 0);
    if (acc == - (n+m)) continue;
    long long ans_tmp {};
    for (int j=0;j<n;++j) {
      if (!(i & (1<<j))) continue;
      ans_tmp += merch[j].second;
    }
    for (int j=0;j<m;++j) {
      if (!(i & (1<<(j+n)))) continue;
      ans_tmp -= magic[j].second;
    }
    ans = max(ans, ans_tmp);
    //print_bit(i);
  }
  cout << ans << '\n';
}
0