Problem p03732 (python)

Fixed submission:
# -*- coding: utf-8 -*-

"""
・メモ化再帰
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from collections import defaultdict

N, W = map(int, input().split())
wN = [0] * N
vN = [0] * N
for i in range(N):
    wN[i], vN[i] = map(int, input().split())

# memo[i][j]: i番目以降の品物から重さの和がj以下なるように選んだときの価値の和の最大値
memo = [defaultdict(lambda: -1) for i in range(N+1)]

def dfs(cur, wei):
    # 既に調べた場所はそのまま返却
    if memo[cur][wei] != -1:
        return memo[cur][wei]
    # 品物を最後まで見た
    if cur == N:
        res = 0
    # まだ余力があるから両方試す
    elif wei >= wN[cur]:
        res = max(dfs(cur+1, wei-wN[cur]) + vN[cur], dfs(cur+1, wei))
    # もうこの回の荷物は入らない
    else:
        res = dfs(cur+1, wei)
    # ここまでのベストな値をメモに記録してから返却
    memo[cur][wei] = res
    return res
# 0番目以降で容量W以下の場合の結果を表示
print(dfs(0, W))

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * (3*(N-1)+100) for i in range(N+1)]

# 答えが明らかな範囲はDPに含めない
if W < wN[0]:
    print(0)
    exit()
elif W >= sum(wN):
    print(sum(vN))
    exit()

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, (3*(N-1)+100) + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * (3*(N-1)+1)+100 for i in range(N+1)]

# 答えが明らかな範囲はDPに含めない
if W < wN[0]:
    print(0)
    exit()
elif W >= sum(wN):
    print(sum(vN))
    exit()

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, (3*(N-1)+1)+100 + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * (3*(N-1)+1)*100 for i in range(N+1)]

# 答えが明らかな範囲はDPに含めない
if W < wN[0]:
    print(0)
    exit()
elif W >= sum(wN):
    print(sum(vN))
    exit()

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, (3*(N-1)+1)*100 + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * (3*(N-1)+1) for i in range(N+1)]

# 答えが明らかな範囲はDPに含めない
if W < wN[0]:
    print(0)
    exit()
elif W >= sum(wN):
    print(sum(vN))
    exit()

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, 3*(N-1)+1 + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * (wN[0]+3)*N for i in range(N+1)]

if W < wN[0]:
    print(0)
    exit()
elif W >= (wN[0]+3)*N:
    print(sum(vN))
    exit()

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, (wN[0]+3)*N + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * (wN[0]+3)*N for i in range(N+1)]

if W < wN[0]:
    print(0)
    exit()
elif W >= (wN[0]+3)*N:
    print(sum(vN))

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, (wN[0]+3)*N + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * ((wN[0]+3)*N - 3) for i in range(N+1)]

if W < wN[0]:
    print(0)
    exit()
elif W >= (wN[0]+3)*N - 3:
    print(sum(vN))

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, (wN[0]+3)*N - 3 + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])