Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

n, w = map(int, input().strip().split())
data = [list(map(int, input().strip().split())) for _ in range(n)]

# i番目に重さがj以下となるように選んだときの価値の総和の最大値
dp = np.zeros((n, w + 1), dtype=np.int64)

for i in range(0, n):
    for j in range(w + 1):
        # i 番目の品物の重さと価値
        wi, vi = data[i]
        if i == 0:
            take = vi if j - wi >= 0 else 0
            miss = 0
            dp[i][j] = max(take, miss)
        else:
            # i番目の品物を入れる場合
            take = dp[i - 1][j - wi] + vi if j - wi >= 0 else 0
            # 入れない場合
            miss = dp[i - 1][j]
            dp[i][j] = max(take, miss)

print(np.max(dp[n - 1]))


Fixed submission:
n, w = map(int, input().strip().split())
data = [list(map(int, input().strip().split())) for _ in range(n)]

# i番目に重さがj以下となるように選んだときの価値の総和の最大値
dp = [[0] * (w + 1) for _ in range(n)]

for i in range(0, n):
    for j in range(w + 1):
        # i 番目の品物の重さと価値
        wi, vi = data[i]
        if i == 0:
            take = vi if j - wi >= 0 else 0
            miss = 0
            dp[i][j] = max(take, miss)
        else:
            # i番目の品物を入れる場合
            take = dp[i - 1][j - wi] + vi if j - wi >= 0 else 0
            # 入れない場合
            miss = dp[i - 1][j]
            dp[i][j] = max(take, miss)

print(max(dp[n - 1]))

Buggy python submission (verdict: Time Limit Exceeded):
n, w = list(map(int, input().strip().split()))
data = []
for i in range(n):
    data.append(list(map(int, input().strip().split())))

dp = {}

# i番目以降から重さをz以下にするように選ぶときの最大の価値
def rec(i, z):
    global dp
    if (i, z) in dp:
        return dp[(i, z)]

    if i == n:
        return 0

    # i 個目のものを入れられない場合
    elif data[i][0] > z:
        ret = rec(i + 1, z)
    else:
        # 入れられる場合、入れるときと入れないときのうち大きい方を返す
        # 入れるとき
        v1 = data[i][1] + rec(i + 1, z - data[i][0])
        # 入れないとき
        v2 = rec(i + 1, z)
        ret = max(v1, v2)
        dp[(i, z)] = ret
    return ret

print(rec(0, w))

Fixed submission:
n, w = map(int, input().strip().split())
data = [list(map(int, input().strip().split())) for _ in range(n)]

# i番目に重さがj以下となるように選んだときの価値の総和の最大値
dp = [[0] * (w + 1) for _ in range(n)]

for i in range(0, n):
    for j in range(w + 1):
        # i 番目の品物の重さと価値
        wi, vi = data[i]
        if i == 0:
            take = vi if j - wi >= 0 else 0
            miss = 0
            dp[i][j] = max(take, miss)
        else:
            # i番目の品物を入れる場合
            take = dp[i - 1][j - wi] + vi if j - wi >= 0 else 0
            # 入れない場合
            miss = dp[i - 1][j]
            dp[i][j] = max(take, miss)

print(max(dp[n - 1]))

Buggy python submission (verdict: Time Limit Exceeded):
n, w = list(map(int, input().strip().split()))
data = []
for i in range(n):
    data.append(list(map(int, input().strip().split())))

dp = {}

# i 個までで重さを z 以下にしたときの最大値
def rec(i, z):
    global dp
    if (i, z) in dp:
        return dp[(i, z)]

    if i < 0:
        ret = 0
    # i 個目のものを入れられない場合
    elif data[i][0] > z:
        ret = rec(i - 1, z)
    else:
        # 入れられる場合、入れるときと入れないときのうち大きい方を返す
        # 入れるとき
        v1 = data[i][1] + rec(i - 1, z - data[i][0])
        # 入れないとき
        v2 = rec(i - 1, z)
        ret = max(v1, v2)
        dp[(i, z)] = ret
    return ret

print(rec(n - 1, w))


Fixed submission:
n, w = map(int, input().strip().split())
data = [list(map(int, input().strip().split())) for _ in range(n)]

# i番目に重さがj以下となるように選んだときの価値の総和の最大値
dp = [[0] * (w + 1) for _ in range(n)]

for i in range(0, n):
    for j in range(w + 1):
        # i 番目の品物の重さと価値
        wi, vi = data[i]
        if i == 0:
            take = vi if j - wi >= 0 else 0
            miss = 0
            dp[i][j] = max(take, miss)
        else:
            # i番目の品物を入れる場合
            take = dp[i - 1][j - wi] + vi if j - wi >= 0 else 0
            # 入れない場合
            miss = dp[i - 1][j]
            dp[i][j] = max(take, miss)

print(max(dp[n - 1]))

Buggy python submission (verdict: Time Limit Exceeded):
n, w = list(map(int, input().strip().split()))
data = []
for i in range(n):
    data.append(list(map(int, input().strip().split())))

dp = {}

# i 個までで重さを z 以下にしたときの最大値
def rec(i, z):
    if (i, z) in dp:
        return dp[(i, z)]

    if i < 0:
        ret = 0
    # i 個目のものを入れられない場合
    elif data[i][0] > z:
        ret = rec(i - 1, z)
    else:
        # 入れられる場合、入れるときと入れないときのうち大きい方を返す
        # 入れるとき
        v1 = data[i][1] + rec(i - 1, z - data[i][0])
        # 入れないとき
        v2 = rec(i - 1, z)
        ret = max(v1, v2)
        dp[(i, z)] = ret
    return ret

print(rec(n - 1, w))

Fixed submission:
n, w = map(int, input().strip().split())
data = [list(map(int, input().strip().split())) for _ in range(n)]

# i番目に重さがj以下となるように選んだときの価値の総和の最大値
dp = [[0] * (w + 1) for _ in range(n)]

for i in range(0, n):
    for j in range(w + 1):
        # i 番目の品物の重さと価値
        wi, vi = data[i]
        if i == 0:
            take = vi if j - wi >= 0 else 0
            miss = 0
            dp[i][j] = max(take, miss)
        else:
            # i番目の品物を入れる場合
            take = dp[i - 1][j - wi] + vi if j - wi >= 0 else 0
            # 入れない場合
            miss = dp[i - 1][j]
            dp[i][j] = max(take, miss)

print(max(dp[n - 1]))

Buggy python submission (verdict: Time Limit Exceeded):
n, w = list(map(int, input().strip().split()))
data = []
for i in range(n):
    data.append(list(map(int, input().strip().split())))

dp = [None] * n

# i 個までで重さを z 以下にしたときの最大値
def rec(i, z):
    if i < 0:
        return 0
    # i 個目のものを入れられない場合
    if data[i][0] > z:
        return rec(i - 1, z)

    # 入れられる場合、入れるときと入れないときのうち大きい方を返す
    # 入れるとき
    v1 = data[i][1] + rec(i - 1, z - data[i][0])
    # 入れないとき
    v2 = rec(i - 1, z)
    return max(v1, v2)

print(rec(n - 1, w))

Fixed submission:
n, w = map(int, input().strip().split())
data = [list(map(int, input().strip().split())) for _ in range(n)]

# i番目に重さがj以下となるように選んだときの価値の総和の最大値
dp = [[0] * (w + 1) for _ in range(n)]

for i in range(0, n):
    for j in range(w + 1):
        # i 番目の品物の重さと価値
        wi, vi = data[i]
        if i == 0:
            take = vi if j - wi >= 0 else 0
            miss = 0
            dp[i][j] = max(take, miss)
        else:
            # i番目の品物を入れる場合
            take = dp[i - 1][j - wi] + vi if j - wi >= 0 else 0
            # 入れない場合
            miss = dp[i - 1][j]
            dp[i][j] = max(take, miss)

print(max(dp[n - 1]))