結果
問題 | No.2364 Knapsack Problem |
ユーザー |
|
提出日時 | 2023-06-30 22:07:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 52 ms / 3,000 ms |
コード長 | 671 bytes |
コンパイル時間 | 126 ms |
コンパイル使用メモリ | 82,324 KB |
実行使用メモリ | 67,328 KB |
最終ジャッジ日時 | 2024-07-07 09:55:08 |
合計ジャッジ時間 | 1,685 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
n,m,w = map(int,input().split())WV = []for i in range(2):A = list(map(int,input().split()))B = list(map(int,input().split()))for a,b in zip(A,B):if i == 0:WV.append([a,b])else:WV.append([-a,-b])inf = 10**10l = n+mdp = [-inf]*(1<<l)dp[0] = 0ans = 0for b in range(1<<l):if dp[b] == -inf:continueans = max(ans,dp[b])size = 0for i in range(l):if b >> i & 1:size += WV[i][0]for i in range(l):if b >> i & 1:continuex,y = WV[i]if 0 <= size+x <= w:dp[b|1<<i] = max(dp[b|1<<i],dp[b]+y)print(ans)