Buggy python submission (verdict: Time Limit Exceeded):

import sys
input = sys.stdin.readline

N,W = map(int,input().split())

nap = []
sum_values = 0
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])
    sum_values += v1

INF = 10**15
dp = list([INF for _ in range(sum_values+1)] for _ in range(N+1))
dp[0][0] = 0

for i in range(N):
    w1, v1 = nap[i]
    for j in range(sum_values+1):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0

for j in range(sum_values+1):
    if dp[N][j] <= W:
        ans = j

print(ans)



Fixed submission:

import sys
input = sys.stdin.readline

N,W = map(int,input().split())

nap = []
sum_values = 0
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])
    sum_values += v1

INF = 10**15
dp = list([INF for _ in range(sum_values+1)] for _ in range(N+1))
dp[0][0] = 0

for i in range(N):
    w1, v1 = nap[i]
    for j in range(sum_values+1):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0

for j in range(sum_values+1):
    if dp[N][j] <= W:
        ans = j

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):


N,W = map(int,input().split())

nap = []
sum_values = 0
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])
    sum_values += v1

INF = 10**15
dp = list([INF for _ in range(sum_values+1)] for _ in range(N+1))
dp[0][0] = 0

for i in range(N):
    w1, v1 = nap[i]
    for j in range(sum_values+1):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0

for j in range(sum_values+1):
    if dp[N][j] <= W:
        ans = j

print(ans)



Fixed submission:

import sys
input = sys.stdin.readline

N,W = map(int,input().split())

nap = []
sum_values = 0
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])
    sum_values += v1

INF = 10**15
dp = list([INF for _ in range(sum_values+1)] for _ in range(N+1))
dp[0][0] = 0

for i in range(N):
    w1, v1 = nap[i]
    for j in range(sum_values+1):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0

for j in range(sum_values+1):
    if dp[N][j] <= W:
        ans = j

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):


N,W = map(int,input().split())

INF = 10**15
dp = list([INF for _ in range(100010)] for _ in range(N+1))
dp[0][0] = 0

nap = []
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])

for i in range(N):
    w1, v1 = nap[i]
    for j in range(100010):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0
for j in range(100001):
    if dp[N][j] <= W:
        ans = j

print(ans)



Fixed submission:

import sys
input = sys.stdin.readline

N,W = map(int,input().split())

nap = []
sum_values = 0
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])
    sum_values += v1

INF = 10**15
dp = list([INF for _ in range(sum_values+1)] for _ in range(N+1))
dp[0][0] = 0

for i in range(N):
    w1, v1 = nap[i]
    for j in range(sum_values+1):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0

for j in range(sum_values+1):
    if dp[N][j] <= W:
        ans = j

print(ans)