結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
![]() |
提出日時 | 2020-08-26 15:49:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 356 ms / 2,000 ms |
コード長 | 765 bytes |
コンパイル時間 | 310 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 222,464 KB |
最終ジャッジ日時 | 2024-11-07 12:02:12 |
合計ジャッジ時間 | 8,420 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
import sys; input = sys.stdin.buffer.readline sys.setrecursionlimit(10**7) from collections import defaultdict con = 10 ** 9 + 7; INF = float("inf") def getlist(): return list(map(int, input().split())) #処理内容 def main(): N = int(input()) DP = [[-INF for i in range(100001)] for j in range(N + 1)] DP[0][0] = 0 for i in range(N): v, w = getlist() for j in range(100001): if DP[i][j] != -INF: DP[i + 1][j] = max(DP[i][j], DP[i + 1][j]) DP[i + 1][j + w] = max(DP[i + 1][j + w], DP[i][j] + v) V = int(input()) m = INF M = INF for i in range(100001): if DP[-1][i] >= V: m = min(m, i) if DP[-1][i] > V and M == INF: M = i - 1 m = max(1, m) if M == INF: M = "inf" print(m) print(M) if __name__ == '__main__': main()