Buggy python submission (verdict: Time Limit Exceeded):
import sys
# inputを高速化する。
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())

dp = [[0 for i in range(W+1)] for j in range(N+1)]


def chmax(a, b):
    if a >= b:
        return a
    else:
        return b

def knapsack(n, w):
    lst_weight = [0 for _ in range(N)]
    lst_value = [0 for _ in range(N)]
    for i in range(N):
        lst_weight[i], lst_value[i] = map(int, input().split())


    for i in range(N):
        for sum_w in range(W+1):
            # i番目の品物を選ぶ
            if sum_w - lst_weight[i] >= 0:
                dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w - lst_weight[i]] + lst_value[i])
            # i番目の品物を選ばない
            dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w])
    
    return dp[n][w]


print(knapsack(N, W))

Fixed submission:

import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)

for _ in range(N):
    w, v = map(int, input().split())
    for wk in range(W, w-1, -1):
        tv = dp[wk - w] + v
        if tv > dp[wk]:
            dp[wk] = tv

print(dp[-1])


Fixed submission:

import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))

Buggy python submission (verdict: Time Limit Exceeded):

import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)

for _ in range(N):
    w, v = map(int, input().split())
    for wk in range(W, w-1, -1):
        tv = dp[wk - w] + v
        if tv > dp[wk]:
            dp[wk] = tv

print(max(dp))

Fixed submission:

import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)

for _ in range(N):
    w, v = map(int, input().split())
    for wk in range(W, w-1, -1):
        tv = dp[wk - w] + v
        if tv > dp[wk]:
            dp[wk] = tv

print(dp[-1])

Fixed submission:

import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

# inputを高速化する。
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())

dp = [0] * (W + 1)

for _ in range(N):
    weight, value = map(int, input().split())
    for wk in range(W, weight-1, -1):
        tv = dp[wk - weight] + value
        if tv > dp[wk]:
            dp[wk] = tv

print(dp[-1])

Fixed submission:

import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

# inputを高速化する。
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
lst_weight_value = [list(map(int, input().split())) for _ in range(N)]

def chmax(a, b):
    if a >= b:
        return a
    else:
        return b

dp = [0] * (W + 1)

for weight, value in lst_weight_value:
    for wk in range(W, weight-1, -1):
        tv = dp[wk - weight] + value
        if tv > dp[wk]:
            dp[wk] = tv

print(dp[-1])

Fixed submission:

import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

# inputを高速化する。
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
# lst_weight = [0 for _ in range(N)]
# lst_value = [0 for _ in range(N)]
# for i in range(N):
#     lst_weight[i], lst_value[i] = map(int, input().split())

def chmax(a, b):
    if a >= b:
        return a
    else:
        return b

dp = [[0 for i in range(W+1)] for j in range(N+1)]

for i in range(N):
    weight, value = map(int, input().split())
    for sum_w in range(W+1):
        # i番目の品物を選ぶ
        if sum_w - weight >= 0:
            dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w - weight] + value)
        # i番目の品物を選ばない
        dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])

Fixed submission:

import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

# inputを高速化する。
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
lst_weight_value = [list(map(int, input().split())) for _ in range(N)]
# print(lst_weight_value)

# def chmax(a, b):
#     if a >= b:
#         return a
#     else:
#         return b

# 重さwの品物の入れ方で達成できる価値の最大値
dp = [0] * (W + 1)

for i in range(N):
    weight, value = lst_weight_value[i]
    for w in range(W, -1, -1):
        _w = w + weight
        _v = dp[w] + value
        if _w > W:
            continue
        if _v <= dp[_w]:
            continue
        dp[_w] = _v

print(dp[-1])

Fixed submission:

import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

# inputを高速化する。
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
lst_weight = [0 for _ in range(N)]
lst_value = [0 for _ in range(N)]
for i in range(N):
    lst_weight[i], lst_value[i] = map(int, input().split())

def chmax(a, b):
    if a >= b:
        return a
    else:
        return b

dp = [[0 for i in range(W+1)] for j in range(N+1)]

for i in range(N):
    for sum_w in range(W+1):
        # i番目の品物を選ぶ
        # print(sum_w - lst_weight[i])
        if sum_w - lst_weight[i] >= 0:
            dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w - lst_weight[i]] + lst_value[i])
        # i番目の品物を選ばない
        dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w])
        # print(dp)

print(dp[N][W])




Fixed submission:

import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))