結果
問題 | No.2364 Knapsack Problem |
ユーザー |
👑 ![]() |
提出日時 | 2023-06-30 22:49:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 94 ms / 3,000 ms |
コード長 | 1,181 bytes |
コンパイル時間 | 718 ms |
コンパイル使用メモリ | 79,280 KB |
最終ジャッジ日時 | 2025-02-15 04:23:56 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <atcoder/modint> using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; void chmax(int& a, int b){ if(a < b) a = b; } int main(){ int N, M, W; cin >> N >> M >> W; vector<int> dp((W+1)<<(N+M), -1001001001); vector<int> A(N); rep(i,N) cin >> A[i]; vector<int> B(N); rep(i,N) cin >> B[i]; vector<int> C(M); rep(i,M) cin >> C[i]; vector<int> D(M); rep(i,M) cin >> D[i]; dp[0] = 0; rep(n,1<<N) rep(m,1<<M) rep(w,W+1){ int val = dp[w<<(N+M) | n<<M | m]; if(val < -501001001) continue; rep(i,N) if(w+A[i] <= W) if(!(n & (1<<i))){ chmax(dp[(w+A[i])<<(N+M) | n<<M | m | 1<<(i+M)], val + B[i]); } rep(i,M) if(w-C[i] >= 0) if(!(m & (1<<i))){ chmax(dp[(w-C[i])<<(N+M) | n<<M | m | 1<<i], val - D[i]); } } int ans = *max_element(dp.begin(), dp.end()); cout << ans << endl; return 0; }