結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
![]() |
提出日時 | 2024-11-16 15:17:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 489 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 76,416 KB |
最終ジャッジ日時 | 2024-11-16 15:18:00 |
合計ジャッジ時間 | 4,055 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
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()) dp = [INF] * (sumv + 1) dp[0] = 0 dp2 = [0] * (sumv + 1) for v, w in VW: for i in reversed(range(sumv - v + 1)): dp[i+v] = min(dp[i+v],dp[i]+w) y = 0 x = max(dp[V],1) if dp[V+1:]: y = min(dp[V+1:]) - 1 print(x) if x > y: print("inf") else: print(y)