結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
![]() |
提出日時 | 2024-11-15 23:52:04 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 536 bytes |
コンパイル時間 | 320 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 102,016 KB |
最終ジャッジ日時 | 2024-11-15 23:52:08 |
合計ジャッジ時間 | 4,339 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 WA * 25 |
ソースコード
N = int(input()) VW = [] sumv = 0 INF = 10 ** 6 minw = INF for i in range(N): v, w = map(int, input().split()) sumv += v VW.append((v, w)) minw = min(w,minw) VW.sort(reverse = True) V = int(input()) dp2 = [0] * (sumv + 1) if V == 0: print(1) print(max(minw-1,1)) exit() for v, w in VW: tmp = INF dp3 = [0] * (sumv + 1) for i in range(sumv - v + 1): dp3[i + v] = max(dp2[i + v], dp2[i] + w) dp2 = dp3 print(dp2[V]) if len(dp2) > V + 1: print(dp2[V + 1] - 1) else: print("inf")