提出 #44227305

ソースコード 拡げる

n, w = map(int, input().split())
wv = [[0, 0]]
for _ in range(n):
    p, v = map(int, input().split())
    wv.append([p, v])
dp = [[-1 for _ in range(w + 1)] for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(w + 1):
        dp[i][j] = dp[i - 1][j]
        p = wv[i][0]
        q = wv[i][1]
        if j - p >= 0 and dp[i - 1][j - p] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - p] + q)
print(max(dp[n]))

提出情報

提出日時
問題 A19 - Knapsack 1
ユーザ harry_arbrebleu
言語 PyPy3 (7.3.0)
得点 1000
コード長 460 Byte
結果 AC
実行時間 582 ms
メモリ 218096 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 1000 / 1000
結果
AC × 3
AC × 25
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, sample_01.txt, sample_02.txt, sample_03.txt
ケース名 結果 実行時間 メモリ
in01.txt AC 77 ms 80636 KiB
in02.txt AC 109 ms 115272 KiB
in03.txt AC 109 ms 115440 KiB
in04.txt AC 108 ms 115480 KiB
in05.txt AC 108 ms 115508 KiB
in06.txt AC 110 ms 115636 KiB
in07.txt AC 486 ms 217768 KiB
in08.txt AC 484 ms 217928 KiB
in09.txt AC 474 ms 217792 KiB
in10.txt AC 483 ms 218096 KiB
in11.txt AC 493 ms 217812 KiB
in12.txt AC 580 ms 217984 KiB
in13.txt AC 542 ms 218092 KiB
in14.txt AC 541 ms 218024 KiB
in15.txt AC 582 ms 217760 KiB
in16.txt AC 582 ms 218056 KiB
in17.txt AC 108 ms 115432 KiB
in18.txt AC 105 ms 115432 KiB
in19.txt AC 108 ms 115628 KiB
in20.txt AC 475 ms 217832 KiB
in21.txt AC 477 ms 218020 KiB
in22.txt AC 493 ms 217788 KiB
sample_01.txt AC 47 ms 61904 KiB
sample_02.txt AC 43 ms 62100 KiB
sample_03.txt AC 53 ms 65860 KiB