Problem p03164 (python)

Fixed submission:
# # Educational DP Contest E
# 方針：dp[i][v] := i-1番目までの物の中から，価値v以上を達成するように選んだ時の重さの最小値

# 入力
N, W = map(int, input().split())
weight = [0] * N
value = [0] * N
for i in range(N):
    w, v = map(int, input().split())
    weight[i] = w
    value[i] = v

# DPテーブル
max_v = sum(value)
dp = [[float("inf")] * (max_v + 1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for v in range(max_v+1):
        if v >= value[i]:       # i番目の物を選ぶ時
            dp[i+1][v] = min(dp[i][v - value[i]] + weight[i], dp[i][v])
        else:
            dp[i+1][v] = dp[i][v]

for v in range(max_v, -1, -1):
    if dp[N][v] <= W:
        ans = v
        break
print(ans)

Buggy submission (verdict: Runtime Error):
# # Educational DP Contest E
# 方針：dp[i][w] := i番目の物の中から，重さwを超えない時の価値の最大値
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
wv.sort()
if N == 1:
    if wv[0][0] <= W:
        print(wv[0][1])
    else:
        print(0)
    exit()

dp = [[0] * (W+1) for _ in range(N+1)]
weight_possible_now = wv[0][0]


for i in range(N):
    if wv[i-1][0] < W:
        dp[i+1][:wv[i][0]] = dp[i][:wv[i][0]]
    weight_possible_now += wv[i][0]
    for w in range(wv[i][0], W+1):
        if weight_possible_now < W and w == weight_possible_now:
            dp[i+1][w+1:] = [dp[i+1][w]] * (W + 1 - w)
            break
        else:
            if w >= wv[i][0]:
                dp[i+1][w] = max(dp[i][w - wv[i][0]] + wv[i][1], dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]
print(dp[N][W])

Buggy submission (verdict: Runtime Error):
# # Educational DP Contest E
# 方針：dp[i][w] := i番目の物の中から，重さwを超えない時の価値の最大値
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
wv.sort()
dp = [[0] * (W+1) for _ in range(N+1)]
weight_possible_now = wv[0][0]
if N == 1:
    if wv[0][0] <= W:
        print(wv[0][1])
    else:
        print(0)
    exit()

for i in range(N):
    if wv[i-1][0] < W:
        dp[i+1][:wv[i][0]] = dp[i][:wv[i][0]]
    weight_possible_now += wv[i][0]
    for w in range(wv[i][0], W+1):
        if weight_possible_now < W and w == weight_possible_now:
            dp[i+1][w+1:] = [dp[i+1][w]] * (W + 1 - w)
            break
        else:
            if w >= wv[i][0]:
                dp[i+1][w] = max(dp[i][w - wv[i][0]] + wv[i][1], dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]
print(dp[N][W])

Buggy submission (verdict: Runtime Error):
# # Educational DP Contest E
# 方針：dp[i][w] := i番目の物の中から，重さwを超えない時の価値の最大値
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
wv.sort()
dp = [[0] * (W+1) for _ in range(N+1)]
weight_possible_now = wv[0][0]
if N == 1:
    if wv[0][0] <= W:
        print(wv[0][1])
    else:
        print(0)
    exit()

for i in range(N):
    if wv[i-1][0] < W:
        dp[i+1][:wv[i][0]] = dp[i][:wv[i][0]]
    weight_possible_now += wv[i][0]
    for w in range(wv[i][0], W+1):
        if weight_possible_now < W and w == weight_possible_now:
            dp[i+1][w+1:] = [dp[i+1][w]] * (W + 1 - w)
            break
        else:
            if w >= wv[i][0]:
                dp[i+1][w] = max(dp[i][w - wv[i][0]] + wv[i][1], dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]
print(dp[N][W])