結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
![]() |
提出日時 | 2022-02-14 21:48:14 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 638 bytes |
コンパイル時間 | 227 ms |
コンパイル使用メモリ | 82,060 KB |
実行使用メモリ | 77,756 KB |
最終ジャッジ日時 | 2024-06-29 06:55:37 |
合計ジャッジ時間 | 4,561 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 WA * 23 |
ソースコード
N = int(input()) VW = [list(map(int, input().split())) for _ in range(N)] V = int(input()) DP = [0]*(100010) DPM = [0]*(100010) for v,w in VW: for i in reversed(range(100010)): if DP[i]>0: DP[i+v]=max(DP[i+v],DP[i]+w) if DPM[i+v]==0: DPM[i+v]=DPM[i]+w else: DPM[i+v]=min(DPM[i+v],DPM[i]+w) DP[v]=max(DP[v],w) if DPM[v]==0: DPM[v]=w else: DPM[v]=min(DPM[v],w) print(max(1,DPM[V])) ma = 10**18 for i in range(V+1,100010): if DP[i]>0 and ma>DP[i]: ma=DP[i] if ma!=10**18: print(ma-1) else: print('inf')