Problem p03734 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 8)

N, W = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
memo = {i : {} for i in range(N)}

def dfs(i, j):
    if i == N:
        return 0
    elif j in memo[i]:
        return memo[i][j]
    elif A[i][0] > j:
        ans = dfs(i + 1, j)
    else:
        ans  = max(dfs(i + 1, j), A[i][1] + dfs(i + 1, j - A[i][0]))
    memo[i][j] = ans
    return ans
        
print(dfs(0, W))

Buggy submission (verdict: Runtime Error):
n, w = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(n)]
dp = [[0] * (w + 1) for i in range(n + 1)]

for i in range(n):
    for j in range(w + 1):
        if j < A[i][0]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - A[i][0]] + A[i][1])
            
print(dp[n][w])

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 8)

N, W = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
dp = [[-1] * (W + 1) for i in range(N + 1)]

def rec(i, w):
    if dp[i][w] >= 0:
        return dp[i][w]
    #すでに調べたことがあるならばその結果を再利用
    #すでにテーブルに記録してあるので、この時点でreturnして良い
    if i == N:
        res = 0
        # テーブルに記録するまで結果をresに保持しておく
    elif w < A[i][0]:
        res = rec(i + 1, w)
    else:
        res = max(rec(i + 1, w), rec(i + 1, w - A[i][0]) + A[i][1])
    dp[i][w] = res
    # 結果をテーブルに記録する
    return res
    # テーブルに記録したのでreturn

print(rec(0, W))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 8)

N, W = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
memo = [[-1] * (W + 1) for i in range(N + 1)]

def dfs(i, j):
    if memo[i][j] >= 0:
        ans = memo[i][j]
    elif i == N:
        ans = 0
    elif A[i][0] > j:
        ans = dfs(i + 1, j)
    else:
        ans  = max(dfs(i + 1, j), A[i][1] + dfs(i + 1, j - A[i][0]))
    memo[i][j] = ans
    return ans
        
print(dfs(0, W))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 8)

N, W = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
memo = [[0] * (W + 1) for i in range(N + 1)]

def dfs(i, j):
    if memo[i][j] != 0:
        ans = memo[i][j]
    elif i == N:
        return 0
    elif A[i][0] > j:
        return dfs(i + 1, j)
    else:
        ans  = max(dfs(i + 1, j), A[i][1] + dfs(i + 1, j - A[i][0]))
        memo[i][j] = ans
    return ans
        
print(dfs(0, W))

Buggy submission (verdict: Runtime Error):
N, W = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
memo = [[0] * (W + 1) for i in range(N + 1)]

def dfs(i, j):
    if memo[i][j] != 0:
        ans = memo[i][j]
    elif i == N:
        return 0
    elif A[i][0] > j:
        return dfs(i + 1, j)
    else:
        ans  = max(dfs(i + 1, j), A[i][1] + dfs(i + 1, j - A[i][0]))
        memo[i][j] = ans
    return ans
        
print(dfs(0, W))

Buggy submission (verdict: Runtime Error):
N, W = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
memo = [[0] * (W + 1) for i in range(N + 1)]

def dfs(i, j):
    if memo[i][j] != 0:
        ans = memo[i][j]
    elif i == N:
        return 0
    elif A[i][0] > j:
        return 0
    else:
        ans  = max(dfs(i + 1, j), A[i][1] + dfs(i + 1, j - A[i][0]))
        memo[i][j] = ans
    return ans
        
print(dfs(0, W))