結果
問題 | No.2364 Knapsack Problem |
ユーザー |
![]() |
提出日時 | 2023-07-01 19:02:49 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,414 bytes |
コンパイル時間 | 4,513 ms |
コンパイル使用メモリ | 141,884 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-08 04:56:21 |
合計ジャッジ時間 | 5,220 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 WA * 10 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <climits>#include <map>#include <queue>#include <set>#include <cstring>#include <vector>using namespace std;typedef long long ll;int main() {int N, M, W;cin >> N >> M >> W;int A[N];int B[N];int C[M];int D[M];for (int i = 0; i < N; ++i) {cin >> A[i];}for (int i = 0; i < N; ++i) {cin >> B[i];}for (int i = 0; i < M; ++i) {cin >> C[i];}for (int i = 0; i < M; ++i) {cin >> D[i];}int dp[W + 1][1 << M];memset(dp, -1, sizeof(dp));int ans = 0;dp[0][0] = 0;for (int i = 0; i < N; ++i) {int a = A[i];int b = B[i];for (int w = W - a; w >= 0; --w) {int nw = w + a;for (int mask = 0; mask < (1 << M); ++mask) {if (dp[w][mask] < 0) continue;dp[nw][mask] = max(dp[nw][mask], dp[w][mask] + b);ans = max(ans, dp[nw][mask]);}}for (int w = W; w >= 0; --w) {for (int mask = 0; mask < (1 << M); ++mask) {if (dp[w][mask] < 0) continue;for (int j = 0; j < M; ++j) {if (mask >> j & 1) continue;int nw = w - C[j];int nmask = mask | (1 << j);if (nw < 0) continue;dp[nw][nmask] = max(dp[nw][nmask], dp[w][mask] - D[j]);}}}}cout << ans << endl;return 0;}