Submission #30845057

Source Code Expand

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)

Submission Info

Submission Time
Task E - Knapsack 2
User Pro_ktmr
Language PyPy3 (7.3.0)
Score 100
Code Size 513 Byte
Status AC
Exec Time 292 ms
Memory 148160 KiB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 21
Set Name Test Cases
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
Case Name Status Exec Time Memory
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