結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
|
提出日時 | 2023-05-04 22:16:59 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 731 bytes |
コンパイル時間 | 591 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 138,660 KB |
最終ジャッジ日時 | 2024-11-22 12:02:05 |
合計ジャッジ時間 | 6,708 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 9 WA * 28 |
ソースコード
INF = 1 << 60 n = int(input()) items = [list(map(int, input().split())) for _ in range(n)] v = int(input()) dp = {} dp[0] = 0 for vi, wi in items: ndp = {} for value, weight in dp.items(): ndp[value] = min(ndp.get(value, INF), weight) if value <= v: ndp[value + vi] = min(ndp.get(value + vi, INF), weight + wi) dp = ndp cands = list(dp.items()) cands.sort(key=lambda x: - x[1]) m = 100001 score = [0] cands.pop() for _ in range(m): score.append(score[-1]) if len(cands) > 0 and len(score) - 1 == cands[-1][1]: score[-1], _ = cands.pop() lb = INF ub = - INF for x in range(1, m + 1): if score[x] == v: lb = min(lb, x) ub = max(ub, x) print(lb) if ub < m: print(ub) else: print("inf")