提出 #30845051

ソースコード 拡げる

n, s = map(int, input().split())
w = [0] * n
v = [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())
INF = 10 ** 18
dp = [[-INF] * (s + 1) for i in range(n + 1)]
# dp: (n + 1) * (s + 1) の 2 次元リスト
dp[0][s] = 0
for i in range(n):
    for j in range(s + 1):
        if j + w[i] <= s:
            dp[i + 1][j] = max(dp[i][j], dp[i][j + w[i]] + v[i])
        else:
            dp[i + 1][j] = dp[i][j]
print(max(dp[n])) # dp[n][0], ..., dp[n][s] の最大値

提出情報

提出日時
問題 D - Knapsack 1
ユーザ Pro_ktmr
言語 PyPy3 (7.3.0)
得点 100
コード長 497 Byte
結果 AC
実行時間 240 ms
メモリ 148136 KiB

ジャッジ結果

セット名 All
得点 / 配点 100 / 100
結果
AC × 13
セット名 テストケース
All 0_00, 0_01, 0_02, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09
ケース名 結果 実行時間 メモリ
0_00 AC 61 ms 61636 KiB
0_01 AC 54 ms 61900 KiB
0_02 AC 49 ms 61772 KiB
1_00 AC 55 ms 65304 KiB
1_01 AC 222 ms 148136 KiB
1_02 AC 219 ms 145312 KiB
1_03 AC 235 ms 146996 KiB
1_04 AC 238 ms 146796 KiB
1_05 AC 238 ms 146736 KiB
1_06 AC 240 ms 147476 KiB
1_07 AC 228 ms 146840 KiB
1_08 AC 207 ms 146340 KiB
1_09 AC 199 ms 147712 KiB