Problem p03734 (python)

Fixed submission:
INFTY = 10**10
N,W = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
dp = [[[-INFTY for _ in range(3*(N-1)+1)] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    for j in range(1,i+1):
        for k in range(3*(N-1)+1):
            dp[i][j][k] = dp[i-1][j][k]
            if k>=X[i-1][0]-X[0][0]:
                dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-X[i-1][0]+X[0][0]]+X[i-1][1])
cmax = 0
for j in range(1,N+1):
    for k in range(3*(N-1)+1):
        if j*X[0][0]+k<=W:
            cmax = max(cmax,dp[N][j][k])
print(cmax)

Buggy submission (verdict: Runtime Error):
INFTY = 10**10
N,W = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
dp = [[[-INFTY for _ in range(3*N+1)] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    for j in range(1,i+1):
        for k in range(3*N+1):
            if i>j:
                dp[i][j][k] = dp[i-1][j][k]
                if k>=X[i-1][0]-X[0][0]:
                    dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-X[i-1][0]+X[0][0]]+X[i-1][1])
            else:
                dp[i][i][k] = dp[i-1][i-1][k-X[i-1][0]+X[0][0]]+X[i-1][1]
cmax = 0
for j in range(1,N+1):
    if W-j*X[0][0]>=0:
        for k in range(W-j*X[0][0]+1):
            cmax = max(cmax,dp[N][j][k])
print(cmax)

Buggy submission (verdict: Runtime Error):
INFTY = 10**10
N,W = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
dp = [[[-INFTY for _ in range(3*N+1)] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    for j in range(1,i+1):
        for k in range(3*N+1):
            dp[i][j][k] = dp[i-1][j][k]
            if k>=X[i-1][0]-X[0][0]:
                dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-X[i-1][0]+X[0][0]]+X[i-1][1])
cmax = 0
for j in range(1,N+1):
    if W-j*X[0][0]>=0:
        for k in range(W-j*X[0][0]+1):
            cmax = max(cmax,dp[N][j][k])
print(cmax)

Buggy submission (verdict: Runtime Error):
INFTY = 10**10
N,W = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
dp = [[[-INFTY for _ in range(301)] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    for j in range(1,i+1):
        for k in range(301):
            dp[i][j][k] = dp[i-1][j][k]
            if k>=X[i-1][0]-X[0][0]:
                dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-X[i-1][0]+X[0][0]]+X[i-1][1])
cmax = 0
for j in range(1,N+1):
    for k in range(W-j*X[0][0]+1):
        cmax = max(cmax,dp[N][j][k])
print(cmax)

Buggy submission (verdict: Runtime Error):
INFTY = 10**8
N,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
w = A[0][0]
C = {i:0 for i in range(4)}
for i in range(N):
    C[A[i][0]-w] += 1
dp = [[[[[-INFTY for _ in range(C[3]+1)] for _ in range(C[2]+1)] for _ in range(C[1]+1)] for _ in range(C[0]+1)] for _ in range(N+1)]
for n in range(N+1):
    dp[n][0][0][0][0] = 0
for n in range(1,N+1):
    for i in range(C[0]+1):
        for j in range(C[1]+1):
            for k in range(C[2]+1):
                for l in range(C[3]+1):
                    dp[n][i][j][k][l] = dp[n-1][i][j][k][l]
                    if A[n-1][0]-w==0:
                        if i>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i-1][j][k][l]+A[n-1][1])
                    elif A[n-1][0]-w==1:
                        if j>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i][j-1][k][l]+A[n-1][1])
                    elif A[n-1][0]-w==2:
                        if k>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i][j][k-1][l]+A[n-1][1])
                    elif A[n-1][0]-w==3:
                        if l>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i][j1][k][l-1]+A[n-1][1])
vmax = 0
for i in range(C[0]+1):
    for j in range(C[1]+1):
        for k in range(C[2]+1):
            for l in range(C[3]+1):
                if (i+j+k+l)*w+j+2*k+3*l<=W:
                    vmax = max(vmax,dp[N][i][j][k][l])
print(vmax)

Buggy submission (verdict: Runtime Error):
INFTY = 10**10
N,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
w = A[0][0]
C = {i:0 for i in range(4)}
for i in range(N):
    C[A[i][0]-w] += 1
dp = [[[[[-INFTY for _ in range(C[3]+1)] for _ in range(C[2]+1)] for _ in range(C[1]+1)] for _ in range(C[0]+1)] for _ in range(N+1)]
for n in range(N+1):
    dp[n][0][0][0][0] = 0
dp[1][1][0][0][0] = A[0][1]
for n in range(2,N+1):
    for i in range(C[0]+1):
        for j in range(C[1]+1):
            for k in range(C[2]+1):
                for l in range(C[3]+1):
                    dp[n][i][j][k][l] = dp[n-1][i][j][k][l]
                    if A[n-1][0]-w==0:
                        if i>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i-1][j][k][l]+A[n-1][1])
                    elif A[n-1][0]-w==1:
                        if j>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i][j-1][k][l]+A[n-1][1])
                    elif A[n-1][0]-w==2:
                        if k>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i][j][k-1][l]+A[n-1][1])
                    elif A[n-1][0]-w==3:
                        if l>=1: dp[n][i][j][k][l]= max(dp[n][i][j][k][l],dp[n-1][i][j1][k][l-1]+A[n-1][1])
vmax = 0
for i in range(C[0]+1):
    for j in range(C[1]+1):
        for k in range(C[2]+1):
            for l in range(C[3]+1):
                if (i+j+k+l)*w+j+2*k+3*l<=W:
                    vmax = max(vmax,dp[N][i][j][k][l])
print(vmax)