提出 #30845057

ソースコード 拡げる

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
sum_v = sum(v)
dp = [[INF] * (sum_v + 1) for i in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(sum_v + 1):
        if j - v[i] >= 0:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
        else:
            dp[i + 1][j] = dp[i][j]
answer = 0
for i in range(sum_v + 1):
    if dp[n][i] <= s:
        answer = i
print(answer)

提出情報

提出日時
問題 E - Knapsack 2
ユーザ Pro_ktmr
言語 PyPy3 (7.3.0)
得点 100
コード長 513 Byte
結果 AC
実行時間 292 ms
メモリ 148160 KiB

ジャッジ結果

セット名 All
得点 / 配点 100 / 100
結果
AC × 21
セット名 テストケース
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, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17
ケース名 結果 実行時間 メモリ
0_00 AC 292 ms 69804 KiB
0_01 AC 54 ms 61752 KiB
0_02 AC 48 ms 61636 KiB
1_00 AC 52 ms 61544 KiB
1_01 AC 186 ms 146420 KiB
1_02 AC 134 ms 106660 KiB
1_03 AC 194 ms 147264 KiB
1_04 AC 132 ms 106404 KiB
1_05 AC 188 ms 145836 KiB
1_06 AC 129 ms 106004 KiB
1_07 AC 188 ms 145676 KiB
1_08 AC 136 ms 106060 KiB
1_09 AC 192 ms 147316 KiB
1_10 AC 132 ms 105740 KiB
1_11 AC 191 ms 146380 KiB
1_12 AC 127 ms 103468 KiB
1_13 AC 191 ms 147304 KiB
1_14 AC 127 ms 102572 KiB
1_15 AC 191 ms 146996 KiB
1_16 AC 136 ms 110596 KiB
1_17 AC 196 ms 148160 KiB