結果
問題 | No.2364 Knapsack Problem |
ユーザー |
|
提出日時 | 2023-06-30 21:43:55 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,027 bytes |
コンパイル時間 | 177 ms |
コンパイル使用メモリ | 82,124 KB |
実行使用メモリ | 76,472 KB |
最終ジャッジ日時 | 2024-07-07 09:24:20 |
合計ジャッジ時間 | 1,968 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 11 WA * 6 RE * 3 |
ソースコード
from itertools import productN, M, W = map(int, input().split())A = list(map(int, input().split()))B = list(map(int, input().split()))C = list(map(int, input().split()))D = list(map(int, input().split()))ans = 0for pr1 in product((0, 1), repeat=N):for pr2 in product((0, 1), repeat=M):Wc = []wi, vi = 0, 0for i in range(N):if pr1[i]:Wc.append(A[i])vi += B[i]for i in range(N):if pr2[i]:Wc.append(-C[i])vi -= D[i]Wc.sort()l, r = 0, len(Wc) - 1while l <= r:# print(l, r, Wc)if 0 <= Wc[l] + wi <= W:wi += Wc[l]l += 1continueelif 0 <= Wc[r] + wi <= W:wi += Wc[r]r -= 1continueelse:breakif l > r:ans = max(ans, vi)# print(pr1, pr2, l == r, ans, Wc)print(ans)