Problem:


Score : 100 points

Problem Statement

There are N items, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), Item i has a weight of w_i and a value of v_i.

Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^9

1 \leq w_i \leq W

1 \leq v_i \leq 10^3

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible sum of the values of items that Taro takes home.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8, and the sum of the values is 30 + 60 = 90.

Sample Input 2

1 1000000000
1000000000 10

Sample Output 2

10

Sample Input 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Sample Output 3

17

Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14, and the sum of the values is 6 + 6 + 5 = 17.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
goods=[list(map(int,input().split())) for _ in range(n)]
DP=[[0]*(w+1) for _ in range(n+1)]
for i in list(range(n))[::-1]:
  wi,vi=goods[i][0],goods[i][1]
  for j in range(w+1):
    if j<wi:
      DP[i][j]=DP[i+1][j]
    else:
      DP[i][j]=max(DP[i+1][j],DP[i+1][j-wi]+vi)
print(DP[0][w])

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
goods=[list(map(int,input().split())) for _ in range(n)]
DP=[[0]*(w+1) for _ in range(n+1)]
for i in list(range(n))[::-1]:
  for j in range(w+1):
    wi,vi=goods[i][0],goods[i][1]
    if j<wi:
      DP[i][j]=DP[i+1][j]
    else:
      DP[i][j]=max(DP[i+1][j],DP[i+1][j-wi]+vi)
print(DP[0][w])

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
goods=[list(map(int,input().split())) for _ in range(n)]
DP=[[0]*(w+1) for _ in range(n+1)]
for i in list(range(n))[::-1]:
  for j in range(w+1):
    wi,vi=goods[i][0],goods[i][1]
    if j<wi:
      DP[i][j]=DP[i+1][j]
    else:
      DP[i][j]=max(DP[i+1][j],DP[i][j-wi]+vi)
print(DP[0][w])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

N, W = [int(item) for item in input().split()]
item = np.array([[int(item) for item in input().split()] for _ in range(N)])

dp = np.zeros((N+1, W+1), dtype='int64')

for i in range(N):
    dp[i+1] = dp[i]
    w, v = item[i]
    np.maximum(dp[i][w:], dp[i][:-w] + v, out=dp[i+1][w:])
    #print(dp)

print(np.max(dp))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
    for j in range(W+1):
        if j-w[i]>=0:
            dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
        dp[i+1][j]=max(dp[i+1][j],dp[i][j])
print(dp[N][W])

Submission status: Runtime Error

Solution code:
# atcoderのテスト用
# ./iunput/input.txt に入力を書き込む
with open('./input/input.txt') as f:
    n, W = map(int, f.readline().split())
    wv = [list(map(int, f.readline().split())) for _ in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
inf = float('inf')
V = max(v)
vmax = 10**5+1
# dp[i][sum_v] 
# := i-1番目までの品物で価値がsum_vを超えないように選んだときの重さの総和の最小値
# 価値の合計はどれくらい大きくなるかわからないので十分に用意しとく
dp = [[inf for _ in range(vmax)] for _ in range(n+1)]
# 初期条件
dp[0][0] = 0
for i in range(n):
    for sum_v in range(vmax):
        # i番目の品物を選べるとき
        #print(f'before: dp[{i}][{sum_v}] = {dp[i][sum_v]}')
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i])
            #print(f'after choosing i: dp[{i}][{sum_v}] = {dp[i][sum_v]}')
        # i番目の品物を選ばないとき
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
        #print(f'after: dp[{i}][{sum_v}] = {dp[i][sum_v]}')

# 最適解を探す
ans = 0
for sum_v in range(vmax):
    if dp[n][sum_v] <= W:
        #print(f'dp[{n}][{sum_v}] = {dp[n][sum_v]}')
        ans = sum_v
#print(dp[n])
print(ans)

Submission status: Runtime Error

Solution code:
import sys


def solve():
    readline = sys.stdin.readline
    N, W = map(int, readline().split())
    WV = (map(int, readline().split()) for _ in range(N))
    dp = [0] * (W+1)
    for w, v in WV:
        for i in range(W, w-1, -1):
            tmp_dp = dp[i-w] + v
            if dp[i] < tmp_dp:
                dp[i] = tmp_dp
    return max(dp)


if __name__ == "__main__":
    answer = solve()
    print(answer)

Submission status: Runtime Error

Solution code:
N,W = [int(i) for i in input().split()]
w = [] # limit weight to knapsack capacity
v = [] # maximize value
for i in range(N):
  line = input().split()
  w.append(int(line[0]))
  v.append(int(line[1]))
mem = [[0]*(W+1) for i in range(N)]
for i in range(w[0], W+1):
  mem[0][i] = v[0]
for i in range(1, N):
  for j in range(1, W+1):
    if w[i] > j:
      mem[i][j] = mem[i-1][j]
    else:
      mem[i][j] = max(mem[i-1][j], v[i] + mem[i-1][j - w[i]])
#print(mem)
print("%s" % mem[N-1][W])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
dp = [[0] * (W+1) for _ in range(N+1)]
w, v = [0]*N, [0]*N
for i in range(N):
    w[i], v[i] = map(int,input().split())
for i in range(N):
    for weight in range(W+1):
        if 0 <= weight - w[i]:
            dp[i+1][weight] = max(dp[i][weight-w[i]]+v[i],dp[i][weight])
        else:
            dp[i+1][weight] = dp[i][w[i]]
print(dp[N][W])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
wv = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: x[0])

# 重さをi、dp[i]を価値の最大値とする
dp = [0]*(W+1)
dp[0] = 0

for i in range(N):
    w, v = wv[i]
    # 前から埋めていくとさっき更新したやつをもとに更新してしまう（同じものを使ってしまう）ので逆から更新する
    for j in range(W, w-1, -1):
        dp[j] = max(dp[j], dp[j-w] + v)

print(dp[W])

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())

dp = [0]*(W+1) # dp[i][w]はi個までの品物を使い、w以下の重さ分詰めたときの価値の最大値

for i in range(N):
    w,v = map(int,input().split())
    for j in range(W+1)[::-1]:
        if j>=w:
            dp[j] = max(dp[j],dp[j-w]+v)
        else:
            dp[j] = dp[j]

print(dp[-1])

Submission status: Runtime Error

Solution code:
# D
N, W = map(int, input().split())
 
import numpy as np

dp = np.zeros(W+1, dtype=int)

for i in range(1, N+1):
    w, v = map(int, input().split())
    dp[w:W+1] = np.maximum(dp[0:W-w+1]+v, dp[w:W+1])

print(dp[-1])

Submission status: Runtime Error

Solution code:
# D
N, W = map(int, input().split())
 
import numpy as np
dp = np.zeros(W+1, dtype="int64")
 
for i in range(1, N+1):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[w:], dp[0:W-w+1] + v)
 
print(dp[-1])

Submission status: Runtime Error

Solution code:
# D
N, W = map(int, input().split())

import numpy as np
dp = np.zeros(W+1, dtype="int64")

for i in range(1, N+1):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[w:], dp[0:W-w+1] + v)

print(dp[-1])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i], v[i] = map(int, input().split())
V = sum(v)

#dp[i][j]...i番目までの品物で価値j以上を達成するのに必要な重さの最小値(達成できないときはinf)
dp = [[float("inf")]*(V+1) for _ in range(N+1)]

for j in range(1,V+1):
    if j<=v[0]:
        dp[1][j] = w[0]

for i in range(2,N+1):
    for j in range(V+1):
        if j<v[i-1]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i-1]+w[i-1]])

ans=0
#print(dp)
for i in range(N+1):
    for j in range(V+1):
        if dp[i][j] <= W:
            ans = j
            break

print(ans)

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
ws = [x[0] for x in s]
v = [x[1] for x in s]

dp = [[0]*(w+1) for _ in range(n+1)]

for sum_w in range(w+1):
    for i in range(1, n+1):
        if ws[i-1] <= sum_w:
            dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-ws[i-1]]+v[i-1])
        else:
            dp[i][sum_w] = dp[i-1][sum_w]

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

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
ws = [x[0] for x in s]
v = [x[1] for x in s]

dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for sum_w in range(w+1):
        if sum_w + ws[i] <= w:
            dp[i+1][sum_w + ws[i]] = max(dp[i+1][sum_w + ws[i]], dp[i][sum_w]+v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
ws = [x[0] for x in s]
v = [x[1] for x in s]

dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for sum_w in range(w+1):
        if sum_w + ws[i] <= w:
            dp[i+1][sum_w + ws[i]] = max(dp[i+1]
                                         [sum_w + ws[i]], dp[i][sum_w]+v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
ws = [x[0] for x in s]
v = [x[1] for x in s]

dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for sum_w in range(w+1):
        if sum_w + ws[i] <= w:
            dp[i+1][sum_w + ws[i]] = max(dp[i+1][sum_w + ws[i]],
                                         dp[i][sum_w]+v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
INF = 10**10 - 1


#指定数分の３つの整数を順番に受けてリストに入力
# スペース区切りの整数入力
N,Wmax = map(int, input().split())
w = [0]*(N+1)
v = [0]*(N+1)
for i in range(1,N+1):
    w[i],v[i] = map(int, input().split())

#dpの初期化
dp = [[-INF] * (Wmax+1) for i in range(N+1)]
for i in range(0,N+1):
    dp[i][0] = 0
#print(dp[0])

for i in range(1,N+1):
    for ww in range(1,Wmax+1):
        if w[i] > ww:
            dp[i][ww] = dp[i-1][ww]        
        else:
            dp[i][ww] = max(dp[i-1][ww],dp[i-1][ww-w[i]]+v[i])
    #print(dp[i])

Vmax = 0
for ww in range(1,Wmax+1):
    Vmax = max(Vmax,dp[N][ww])
print(Vmax)

Submission status: Runtime Error

Solution code:
def main():
    n,lim_w=map(int,input().split())
    wv = []
    for _ in range(n):
        tmp = list(map(int,input().split()))
        wv.append(tmp)
    dp = [[0] * (lim_w+1) for i in range(n+1)]

    for i in range(0, n):
        for w in range(0,lim_w+1):
            if w >= wv[i][0]:
                dp[i+1][w] = max(dp[i][w], dp[i][w-wv[i][0]] + wv[i][1])
            else:
                dp[i+1][w] = dp[i][w]

    print(dp[n][lim_w])
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
[n,w] = [int(i) for i in input().split()]
w_v = []
for i in range(n):
    w_v.append([int(j) for j in input().split()])

"""
dp[i][v] = w
i : 何番目までのものを使うか
v : ちょうどその価値になる
w : その時の重さ
最後に後ろから全探索して重さ超えてないやつ探す？
"""
INF = 10 ** 9 + 7
v_max = 10**3 * n
dp = [[INF] * (v_max) for i in range(n)]
##print(dp)
#価値0になるところの重さは0
for i in range(n):
    dp[i][0] = 0

for i in range(n):
    #print("step",i)
    if i != 0:
        for v_zantei in range(v_max):
            if v_zantei >= w_v[i][1]:
                dp[i][v_zantei] = min(dp[i-1][v_zantei],dp[i-1][v_zantei - w_v[i][1]] + w_v[i][0])
            else:
                dp[i][v_zantei] = dp[i-1][v_zantei]
        #print(dp[i])
    else:
        dp[i][w_v[i][1]] = w_v[i][0]
        #print(dp[i])
ans = -1
for v in range(v_max-1,-1,-1):
    #print(w,dp[n-1][v],ans)
    if dp[n-1][v] <= w and ans < v:
        ##print(v)
        ans = v
print(ans)

Submission status: Runtime Error

Solution code:
[n,w] = [int(i) for i in input().split()]
w_v = []
for i in range(n):
    w_v.append([int(j) for j in input().split()])

"""
dp[i][v] = w
i : 何番目までのものを使うか
v : ちょうどその価値になる
w : その時の重さ
最後に後ろから全探索して重さ超えてないやつ探す？
"""
INF = 20
v_max = 20
dp = [[INF] * (v_max) for i in range(n)]
##print(dp)
#価値0になるところの重さは0
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    #print("step",i)
    if i != 0:
        for v_zantei in range(v_max):
            if v_zantei >= w_v[i][1]:
                dp[i][v_zantei] = min(dp[i-1][v_zantei],dp[i-1][v_zantei - w_v[i][1]] + w_v[i][0])
            else:
                dp[i][v_zantei] = dp[i-1][v_zantei]
        #print(dp[i])
    else:
        dp[i][w_v[i][1]] = w_v[i][0]
        #print(dp[i])
ans = -1
for v in range(v_max-1,-1,-1):
    #print(w,dp[n-1][v],ans)
    if dp[n-1][v] <= w and ans < v:
        ##print(v)
        ans = v
print(ans)

Submission status: Runtime Error

Solution code:
N, WW = map(int, input().split())
W = [0] * N
V = [0] * N
for i in range(N):
    w, v = map(int, input().split())
    W[i] = w
    V[i] = v
dp = [[0]*(WW+1) for _ in range(N+1)]
for n in range(1, N+1):
    w = W[n-1]
    v = V[n-1]
    for sum_w in range(WW+1):
        if sum_w <= WW - w:
            # n番目の商品を選ぶ
            dp[n][sum_w+w] = max(dp[n-1][sum_w] + v, dp[n][sum_w+w])
        dp[n][sum_w] = max(dp[n-1][sum_w], dp[n][sum_w])
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
wv=[[int(i) for i in input().split()]for _ in range(n)]

dp=[0]*(w+1)
dp[wv[0][0]]=wv[0][1]
for i in range(1,n):
    ww = wv[i][0]
    v = wv[i][1]
    for j in range(w,ww-1,-1):
        dp[j]=max(dp[j],dp[j-ww]+v)
print(max(dp))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())

import numpy as np
dp = np.zeros(W + 1, dtype='int64')

for i in range(1, N + 1):
    w, v = map(int, input().split())
    dp[w:W+1] = np.maximum(dp[w:W+1], dp[:W-w+1] + v)

print(dp[-1])

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
K = 10**5
dp = [[10**100 for i in range(K+1)] for j in range(N)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = map(int,input().split())
    for j in range(K+1):
        if j < v:
            continue
        else:
            dp[i][j] = min(dp[i-1][j-v] + W,dp[i][j])
for i in range(K+1):
    x = dp[N][-i-1]
    if x <= W:
        print(K-i)
        quit()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #整数1つinput
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii())
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #文字列1つinput
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

n,w = mii()
wei,val= [0],[0]
for _ in range(n):
    p,q=mii()
    wei.append(p)
    val.append(q)

dp = [[0]*(w+1) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,w+1):
        if wei[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j-wei[i]]+val[i],dp[i-1][j])


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

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
minw = min(wv)[0]
l = [0] * (n + 1)
for i in range(n + 1):
    l[i] = [0] * (w - minw + 1)
for i in range(1, n + 1):
    for j in range(w - minw + 1):
        if wv[i - 1][0] <= j + minw:
            if j - wv[i - 1][0] >= 0:
                l[i][j] = max(l[i - 1][j], l[i - 1][j - wv[i - 1][0]] + wv[i - 1][1])
            else:
                l[i][j] = max(l[i - 1][j], wv[i - 1][1])
        else:
            l[i][j] = l[i - 1][j]
print(l[n][w - minw])

Submission status: Runtime Error

Solution code:
xy = [] # (x, y) の配列
for _ in range(n):
    xy.append(tuple(map(float, input().split())))

# g[i][j] := the distance between i and j
g = [[math.sqrt((xy[i][0] - xy[j][0]) ** 2 + (xy[i][1] - xy[j][1]) ** 2) for j in range(n)] for i in range(n)]
t = 0
change = 0

def score(a): # aのスコアを計算する。aは目的地を辿る順に並べた長さnの配列
    s = 0.0
    for i in range(n):
        s += g[a[i]][a[(i + 1) % n]]
    return s

def gen_neighbor(a):#　ランダムに i,j を選んでスワップ
    i = random.randrange(n)
    j = random.randrange(n)
    b = a.copy()
    b[i], b[(i + j) % n] = a[(i + j) % n], a[i]
    return b

start_time = time.time()
a = list(range(n)) # 初期解 a=[0,1,...,n-1]
maxscore = 100000
for i in range(10):
    while time.time() - start_time < (i + 1) * 0.5:
        # 5秒まで0.5秒ずつ山登りした中で最も良い解を採用
        b = gen_neighbor(a)
        if score(a) > score(b): # aより良い解なら採用
            a = b
    if maxscore > score(a):
        a1 = a.copy()
    random.shuffle(a)
while time.time() - start_time < 10: # 10秒まで山登り
    b = gen_neighbor(a1)
    if score(a1) > score(b): # aより良い解なら採用
        a1 = b
print(score(a1))
print(" ".join(map(str, a1)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print(max(dp))

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
WV = []
for i in range(N):
    WV.append(list(map(int,input().split())))
dp = [[] for i in range(N)]
dp[0].append((0,0))
for i in range(N):
    if i == 0:
        dp[i].append((0,0))
        if W >= WV[i][0]:
            dp[i].append((WV[i][0],WV[i][1]))
    else:
        dp[i].append((e1,e2))
        for e1,e2 in dp[i-1]:
            if W >= e1+WV[i][0]:
                dp[i].append((e1+WV[i][0],e2+WV[i][1]))
ans = 0
for e1,e2 in dp[-1]:
    ans = max(e2,ans)
print(ans)

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
minw = min(wv)[0]
l = [0] * (n + 1)
for i in range(n + 1):
    l[i] = [0] * (w - minw + 1)

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
minw = min(wv)[0]
l = [0] * (n + 1)
for i in range(n + 1):
    l[i] = [0] * (w - minw + 1)
for i in range(1, n + 1):
    for j in range(w - minw + 1):
        if wv[i - 1][0] <= j + minw:
            if j - wv[i - 1][0] >= 0:
                l[i][j] = max(l[i - 1][j], l[i - 1][j - wv[i - 1][0]] + wv[i - 1][1])
            else:
                l[i][j] = max(l[i - 1][j], wv[i - 1][1])
        else:
            l[i][j] = l[i - 1][j]
print(l[n][w - minw])

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
l = [0] * (n + 1)
for i in range(n + 1):
    l[i] = [0] * w
for i in range(1, n + 1):
    for j in range(w):
        if wv[i - 1][0] <= j:
            l[i][j] = max(l[i - 1][j], l[i - 1][j + 1 - wv[i - 1][0]] + wv[i - 1][1])
        else:
            l[i][j] = l[i - 1][j]
print(l[n][w - 1])

Submission status: Runtime Error

Solution code:
w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
l = [0] * (n + 1)
for i in range(n + 1):
    l[i] = [0] * w
for i in range(1, n + 1):
    for j in range(w):
        if wv[i - 1][0] <= j:
            l[i][j] = max(l[i - 1][j], (l[i - 1][j + 1 - wv[i - 1][0]] + wv[i - 1][1]))
        else:
            l[i][j] = l[i - 1][j]
print(l[n][w - 1])

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
l = [0] * (n + 1)
for i in range(n + 1):
    l[i] = [0] * w
for i in range(1, n + 1):
    for j in range(w):
        if wv[i - 1][0] <= j:
            l[i][j] = max(l[i - 1][j], l[i - 1][j - wv[i - 1][0]] + wv[i - 1][1])
        else:
            l[i][j] = l[i - 1][j]
print(l[n][w - 1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

N, W = list(map(int, input().split()))
item_list = []

for _ in range(N):
    w, v = list(map(int, input().split()))
    item_list.append((w, v))

dp_table = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    w, v = item_list[i - 1]
    for j in range(W + 1):
        # 品物iを入れない場合
        before_best_value = dp_table[i - 1][j]
        dp_table[i][j] = before_best_value
        # 品物iを入れる場合
        if j - w < 0:
            continue
        value = dp_table[i - 1][j - w] + v
        best_value = max(before_best_value, value)
        dp_table[i][j] = best_value

ans = max(dp_table[-1])
print(ans)

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
L = sorted([list(map(int,input().split())) for i in range(N)])

dp = [0] * (W + 1)
con = 0

for w, v in L:
  con += w
  for i in range(min(con, W), w - 1, -1):
    if dp[i] < dp[i - w] + v:
      dp[i] = dp[i - w] + v

print(max(dp))

Submission status: Runtime Error

Solution code:
import numpy as np
n, w = map(int, input().split())
dp = np.zeros(w+1)

for i in range(1,n+1): #n個の荷物をそれぞれ持つか否か
  wn, vn = map(int, input().split())
  dp[wn:] = np.maximum(dp[wn:], dp[:-wn]+vn)#wnより小さい=>持てない=>価値変わらない
print(int(dp[-1]))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=np.int)
for n in range(1,N+1):
  wn, vn = map(int, input().split())
  dp[wn:]=np.maximum(dp[wn:], dp[:-wn]+vn)
print(dp[W])

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,W = inpl()
value = []
weight = []
for i in range(n):
    a,b = inpl()
    value.append(a)
    weight.append(b)
dp = [[0 for i in range(n+5)] for j in range(W+5)]
for i in range(n):
    for w in range(W+1):
        if w >= weight[i]:
            dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[n][w])

# n=6
# (weight,value)=(2,3),(1,2),(3,6),(2,1),(1,3),(5,85)
# W=8

# >> 91

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
lst = [[0, 0]] 
for i in range(N):
    lst.append(list(map(int, input().split())))
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(1, N+1):
    for j in range(1, W+1):
        if j - lst[i][0] >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-lst[i][0]]+lst[i][1])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import numpy as np

EDPC = "https://atcoder.jp/contests/DP/"
TDPC = "https://atcoder.jp/contests/tDPc/tasks"

############### TESTCASE ###############
test = ""
#test = \
"""
3 8
3 30
4 50
5 60
ans 90
"""

"""
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
ans 5000000000(>int32)
"""

"""
6 15
6 5
5 6
6 4
6 6
3 5
7 2
ans 17
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################
#np.maximum(*arrays) == np.max(np.vstack(*arrays), axis=0)
#(np.maximum(np.array([1,3,2]), np.array([2, 1, 3])) == 
# np.max(np.vstack([np.array([1,3,2]), np.array([2, 1, 3])]), axis=0)).all()
################# MAIN #################

N, W = map(int, input2().split())
WV = np.array([tuple(map(int, input2().split())) for _ in range(N)])

dp = np.zeros(W + 1)
for w, v in WV:
    dp[W:w-1:-1] = np.max(np.vstack([dp[W:w-1:-1], dp[W-w::-1] + v]), axis=0)
    
print(dp[-1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import numpy as np

EDPC = "https://atcoder.jp/contests/DP/"
TDPC = "https://atcoder.jp/contests/tDPc/tasks"

############### TESTCASE ###############
test = ""
#test = \
"""
3 8
3 30
4 50
5 60
ans 90
"""

"""
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
ans 5000000000(>int32)
"""

"""
6 15
6 5
5 6
6 4
6 6
3 5
7 2
ans 17
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################
#np.maximum(*arrays) == np.max(np.vstack(*arrays), axis=0)
#(np.maximum(np.array([1,3,2]), np.array([2, 1, 3])) == 
# np.max(np.vstack([np.array([1,3,2]), np.array([2, 1, 3])]), axis=0)).all()
################# MAIN #################

N, W = map(int, input2().split())
WV = np.array([tuple(map(int, input2().split())) for _ in range(N)], dtype="int64")

dp = np.zeros(W + 1, dtype="int64")
for w, v in WV:
    dp[W:w-1:-1] = np.max(np.vstack([dp[W:w-1:-1], dp[W-w::-1] + v]), axis=0)
    
print(dp[-1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import numpy as np

EDPC = "https://atcoder.jp/contests/DP/"
TDPC = "https://atcoder.jp/contests/tDPc/tasks"

############### TESTCASE ###############
test = ""
#test = \
"""
3 8
3 30
4 50
5 60
ans 90
"""

"""
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
ans 5000000000(>int32)
"""

"""
6 15
6 5
5 6
6 4
6 6
3 5
7 2
ans 17
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################
#np.maximum(*arrays) == np.max(np.vstack(*arrays), axis=0)
(np.maximum(np.array([1,3,2]), np.array([2, 1, 3])) == 
 np.max(np.vstack([np.array([1,3,2]), np.array([2, 1, 3])]), axis=0)).all()
################# MAIN #################

N, W = map(int, input2().split())
WV = np.array([tuple(map(int, input2().split())) for _ in range(N)], 
               dtype="int64")

dp = np.zeros(W + 1, dtype="int64")
for w, v in WV:
    dp[W:w-1:-1] = np.max(np.vstack([dp[W:w-1:-1], dp[W-w::-1] + v]), axis=0)
    
print(dp[-1])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i], v[i] = map(int, input().split())
vmax = max(v)
dp = [[0]*(N * vmax + 1) for i in range(N + 1)]
dp[0][0] = 0
for j in range(N * vmax):
    dp[0][j + 1] = float("inf")

for i in range(N):
    for j in range(N * vmax + 1):
        if j < v[i]:
            dp[i + 1][j] = dp[i][j]
        else: 
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])

ans = 0
for j in range(N*vmax):
    if dp[N][j] <= W:
        ans = j
print(ans

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())

dp = [[float('inf') for _ in range(10**5+1)] for i in range(n)]

v_sum = 0

for i in range(n):
    wi, vi = map(int, input().split())
    v_sum += vi
    if i == 0:
        dp[i][0] = 0
        dp[i][vi] = wi
    else:
        for k in range(v_sum+1):
            if k < vi:
                dp[i][k] = dp[i-1][k]
            else:
                dp[i][k] = min(dp[i-1][k], dp[i-1][k-vi]+wi)

for i in range(v_sum+1,-1,-1):
    if dp[n-1][i] <= w:
        print(i)
        exit()

Submission status: Runtime Error

Solution code:
import sys
import pdb
input = sys.stdin.readline

N, W = map(int, input().split())
ws = [0]
vs = [0]

for _ in range(N):
  w, v = map(int, input().split())
  ws.append(w)
  vs.append(v)

inf = 2e11
V = int(sum(vs))   # N * max(vs)
# V = int(100 * 1e3)   # N * max(vs)
# Weight[i番目までの品番][価値j]
Weight = [[inf for _ in range(V+1)] for __ in range(N+1)]

if ws[1] <= W:
  Weight[1][vs[1]] = ws[1]
  value_max = vs[1]
else:
  value_max = 0

for _ in range(N+1):
  Weight[_][0] = 0

pdb.set_trace()

for num in range(2, N+1):
  for value in range(1, V+1):
    if value >= vs[num]:   # 新しい品物を入れられるとき
      Weight[num][value] = min(Weight[num][value], Weight[num-1][value], Weight[num-1][value-vs[num]] + ws[num])
      if Weight[num][value] <= W:
        value_max = max(value_max, value)
      else:
        Weight[num][value] = inf
    else:   # 新しい品物を入れられないとき
      # 重さを変えることはできない
      Weight[num][value] = Weight[num-1][value]
      # Weight[num][value] = max(Weight[num][value], Weight[num-1][value])

# print(Weight)
print(value_max)

Submission status: Runtime Error

Solution code:
 N, W = map(int, input().split())

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
weight = []
value = []
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    for sum_w in range(W+1):
        # i 番目の品物を選ぶ場合
        if sum_w >= weight[i]:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - weight[i]] + value[i])
        # i 番目の品物を選ばない場合
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy

# 入力
N, W = map(int, input().split())
H = []
H.append([0,0])
for _ in range(N) :
  S = str(input())
  H.append(list(map(int, S.split())))
#index
Hw = 0
Hv = 1

#print (H)
#Vmax = (10**3) * N
Vmax = (60) * N

#合計価値viのときの最小重量
dp = [[sys.maxsize for _ in range(Vmax+1)] for _ in range(N+1)]


for i in range(1, N+1) :
  if i == 1 : 
    dp[i][H[i][Hv]] = H[i][Hw]
  else :
    dp[i][H[i][Hv]] = min(H[i][Hw], dp[i][H[i][Hv]])
    for j in range(Vmax+1) :
      if dp[i-1][j] != sys.maxsize and (j + H[i][Hv]) <= Vmax+1 :
        dp[i][j + H[i][Hv]] = min(dp[i-1][j + H[i][Hv]], dp[i][j] + H[i][Hw])
  #print (dp[i][:])
  out = copy.deepcopy(dp[i][:])
  line = ""
  for x in range(len(out)) :
      if out[x] == sys.maxsize :
        line += "_" + " "
      else :    
        line += str(out[x]) + " "
  print(line)

for k in range(Vmax) :
  if dp[N][Vmax-k] <= W :
    print(Vmax-k)
    exit()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=int)

for i in range(N):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w]+v)
print(dp[-1])

Submission status: Runtime Error

Solution code:
import collections


MAX_N = 110
MAX_V = 100100

Item = collections.namedtuple("Item", ("weight", "value"))


def main():
    N, W = [int(i) for input().split()]
    items = [Item(int(i), int(j)) for (i, j) in [input().split() for _ in range(N)]]
    dp = [[float('inf')] * MAX_V for _ in range(MAX_N)]

    dp[0][0] = 0

    for i in range(N):
        item = items[i]
        for sum_v in range(MAX_V):
            # i番目の品物を選ぶ
            if sum_v - item.value >= 0:
                dp[i + 1][sum_v] = max(dp[i + 1][sum_v], dp[i][sum_v - item.value] + item.weight)
            dp[i + 1][sum_v] = max(dp[i + 1][sum_v], dp[i][sum_v])

    ans = 0
    for sum_v in range(MAX_V):
        if dp[N][sum_v] <= W:
            ans = sum_v

    print(ans)

if __name__ == '__main__':
    main()