結果
問題 | No.2364 Knapsack Problem |
ユーザー | shinchan |
提出日時 | 2023-06-30 21:38:13 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 3,000 ms |
コード長 | 1,521 bytes |
コンパイル時間 | 1,996 ms |
コンパイル使用メモリ | 207,900 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-07 09:15:55 |
合計ジャッジ時間 | 2,328 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define all(v) (v).begin(),(v).end() #define pb(a) push_back(a) #define rep(i, n) for(int i=0;i<n;i++) #define foa(e, v) for(auto& e : v) using ll = long long; const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60); #define dout(a) cout<<fixed<<setprecision(10)<<a<<endl; void chmax(ll &a, ll b) { a = max(a, b); } int main() { cin.tie(0); ios::sync_with_stdio(false); ll n, m, w; cin >> n >> m >> w; vector<ll> a(n), b(n), c(m), d(m); rep(i, n) cin >> a[i]; rep(i, n) cin >> b[i]; rep(i, m) cin >> c[i]; rep(i, m) cin >> d[i]; ll ans = 0; int mask1 = 1 << n; int mask2 = 1 << m; vector<vector<ll>> dp(mask1, vector<ll>(mask2, -INF)); dp[0][0] = 0; rep(bit1, mask1) { rep(bit2, mask2) { ll sum = 0; rep(i, n) if(bit1 >> i & 1) sum += a[i]; rep(i, m) if(bit2 >> i & 1) sum -= c[i]; if(sum < 0 || sum > w) continue; rep(i, n) { if(bit1 >> i & 1) { continue; } if(a[i] + sum <= w) chmax(dp[bit1 ^ (1 << i)][bit2], dp[bit1][bit2] + b[i]); } rep(i, m) { if(bit2 >> i & 1) { continue; } if(-c[i] + sum >= 0LL) chmax(dp[bit1][bit2 ^ (1 << i)], dp[bit1][bit2] - d[i]); } chmax(ans, dp[bit1][bit2]); } } cout << ans << endl; return 0; }