結果

問題 No.2364 Knapsack Problem
ユーザー KoseT
提出日時 2023-07-01 19:39:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,933 bytes
コンパイル時間 2,289 ms
コンパイル使用メモリ 204,780 KB
最終ジャッジ日時 2025-02-15 05:26:14
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 WA * 16
権限があれば一括ダウンロードができます

ソースコード

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