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:
import math
N, W = map(int, input().split())
A = list()
for n in range(N):
	A.append(list(map(int, input().split())))
g = math.gcd(W, A[0][0]) 
for a in range(1, N):
	g = math.gcd(g, A[a][0])
W = W//g 
# print(g)
dp = [[0 for w in range(W+1)] for n in range(N+1)]
for i in range(W+1):
	dp[0][i] = 0
for p in range(1, N+1):
	for q in range(W+1):
		dp[p][q] = dp[p-1][q]
		if (A[p-1][0]//g <= q):
			dp[p][q] = max(dp[p][q], dp[p-1][q - (A[p-1][0]//g)] + A[p-1][1])
# print(dp)
print(dp[N][W])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def solve():
    N, M = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(N)]
    dp = [[0] * (M+1) for i in range(N+1)]
    
    for i in range(N):
        for s in range(M+1):
            a, b = A[i]
            if s-a >= 0:
                dp[i+1][s] = max(dp[i+1][s], dp[i][s-a] + b)
            dp[i+1][s] = max(dp[i+1][s], dp[i][s])
    return dp[N][M]

print(solve())

Submission status: Runtime Error

Solution code:
max_Vi = 10**3
max_Wi = W
import sys
input = sys.stdin.readline
import numpy as np
N,W=map(int,input().split())
dp=[0]+[max_Wi+1]*(N*max_Vi)
dp=np.array(dp)
for i in range(N):
  wi,vi=map(int,input().split())
  dp[vi:]=np.minimum(dp[vi:],dp[:-vi]+wi)
print(np.max(np.where(dp <= W)))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N,W=map(int,input().split())
max_Vi = 10**3
max_Wi = W
dp=[max_Wi+1]*(N*max_Vi+1)
dp[0]=0
for i in range(N):
  wi,vi=map(int,input().split())
  dp[vi:]=np.minimum(dp[vi:],dp[:-vi]+wi)
print(np.max(np.where(dp <= W)))

Submission status: Runtime Error

Solution code:
import numpy as np  

n, w = map(int, input().split())
dp = np.full(n*1000+1, float('inf'))
dp[0] = 0

for _ in range(n):
    weight, value = map(int, input().split())
    dp[:value] = np.minimum(dp[:value], dp[:-value] + weight) 

print(dp[-1])

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
w = []
v = []
for _ in range(N):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)
dp = [[10000000000000 for _ in range(1000 * N + 10)] for _ in range(N + 1) ]
ans = 0
for i in range(N):
    dp[i][0] = 0
for i in range(N):
    for j in range(N * 1000):
        dp[i + 1][j + v[i]] = min(dp[i+1][j+v[i]],dp[i][j]+w[i])
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
for i in range(N * 1000 + 1):
    if dp[N][i] <= W:
        ans = max(ans,i)
print(ans)

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
w = []
v = []
for _ in range(N):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)
dp = [[10000000000000 for _ in range(100 * N + 10)] for _ in range(110) ]
ans = 0
for i in range(N):
    dp[i][0] = 0
for i in range(N):
    for j in range(N * 100):
        dp[i + 1][j + v[i]] = min(dp[i+1][j+v[i]],dp[i][j]+w[i])
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
for i in range(N * 100 + 1):
    if dp[N][i] <= W:
        ans = max(ans,i)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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 = np.zeros((W + 1), dtype=np.uint64)

for _w, _v in zip(w, v):
	np.maximum(dp[_w:], dp[:-_w] + _v, out=dp[_w:])
print(dp[-1])

Submission status: Runtime Error

Solution code:
firstline = str(input())
firstline = firstline.split()
item = int( firstline[0] )
totalweight = int ( firstline[1] )
gh = [0] * (totalweight + 1)
dp = [gh[::] for _ in range(item) ]
total = []

def sort_tuple(tup):  
  
    tup.sort(key = lambda x: x[0])  
    return tup  

for i in range(item):    
    getIn = str(input())
    getIn = getIn.split()
    total.append( ( int( int(getIn[0]) ), int( getIn[1]) ) )
    
sort_tuple(total)
#print(total)

firstStone = total[0]
for i in range(firstStone[0], totalweight+1 ):
    dp[0][i] = firstStone[1]

for i in range(1, item):
    currentStone = total[i]
    currentStoneWeight = currentStone[0]
    currentStoneValue = currentStone[1]
    for j in range(0, totalweight + 1):
        dp[i][j] = max( dp[i - 1][j], dp[i][j]   )
        if j >= currentStoneWeight:
            dp[i][j] = max( dp[i][j], currentStoneValue + dp[i - 1][j - currentStoneWeight] )
#print(dp)
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
np.infimport sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    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()) 

    sum_v = sum(v)

    # dp[i][j]: 0〜(i-1)まで使ったときの価値jのときの重みの総和の最小値
    dp = [[sum(w)]*(sum_v+1) for i in range(N+1)]
    dp[0][0] = 0

    for i in range(1, N+1):
        for j in range(sum_v+1):
            if j-v[i-1] >= 0:
                dp[i][j] = min(dp[i-1][j-v[i-1]] + w[i-1], dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]

    print(max([i for i, w in enumerate(dp[N]) if w<=W]))

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
# 参考：https://atcoder.jp/contests/dp/submissions/5316523

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())

import numpy as np

ndp = np.zeros(W + 1, dtype=np.int64)

# print(ndp)

for w, v in zip(w, v):
    #    print(w,v,ndp[:-w] + v)
    #    print(w,v,ndp[w:])
    np.maximum(ndp[:-w] + v, ndp[w:], out=ndp[w:])
#    print(w,v,ndp)

print(ndp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np

n, w = list(map(int,input().split()))
w_v = [list(map(int,input().split())) for i in range(n)]
#dp = [[0] * (10**9+1) for i in range(101)]
dp = np.zeros((100,10**9+1),dtype=np.int64)

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

    dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[n][w])

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
Wlist=[]
Vlist=[]
for i in range(N):
  w,v=map(int,input().split())
  Wlist+=[w]
  Vlist+=[v]
dp=[[0 for p in range(V+1)] for i in range(N)]
for i in range(V+1):
  if i<=Vlist[0]:
    dp[0][i]=Wlist[0]
for i in range(1,N):
  vi=Vlist[i]
  for j in range(V+1):
    if j-vi>=0:
      dp[i][j]=min(dp[i-1][j-vi]+Wlist[i],dp[i-1][j])
    else:
      dp[i][j]=min(dp[i-1][j],dp[i][j])
dpn=dp[N-1]
ans=0
for i in range(V+1):
  if dpn[i]<=W:
    ans=i
print(ans)

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
Wlist=[]
Vlist=[]
for i in range(N):
  w,v=map(int,input().split())
  Wlist+=[w]
  Vlist+=[v]
dp=[[0 for p in range(V+1)] for i in range(N)]
for i in range(V+1):
  if i<=Vlist[0]:
    dp[0][i]=Wlist[0]
for i in range(1,N):
  vi=Vlist[i]
  for j in range(V+1):
    if j-vi>=0:
      dp[i][j]=min(dp[i-1][j-vi]+Wlist[i],dp[i-1][j])
    else:
      dp[i][j]=min(dp[i-1][j],dp[i][j])
dpn=dp[N-1]
ans=0
for i in range(V+1):
  if dpn[i]<=W:
    ans=i
print(max(dp[N-1]))

Submission status: Runtime Error

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

MAX_V = N * (10 ** 3)
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [10**9+7 for _ in range(MAX_V + 1)]
dp[0] = 0

for w, v in range(N):
    for j in range(MAX_V + 1):
        if j - v >= 0:
            dp[j] = min(dp[j],dp[j - v] + w)
        else:
            dp[j] = dp[j]

mv = 0
for i in range(MAX_V + 1):
    if dp[i] <= W:
        mv = i

print(mv)

Submission status: Runtime Error

Solution code:
def main():

    n, w = map(int, input().split())

    INF = 10 ** 20
    dp = [INF] * (n * 1000)
    dp[0] = 0

    max_vi = 0
    for _ in range(n):
        wi, vi = map(int, input().split())
        max_vi += vi

        for vj in range(max_vi + 1, vi - 1, -1):
            nw = dp[vj - vi] + wi
            if dp[vj] > nw:
                dp[vj] = nw

    for i in range(max_vi, -1, -1):
        if dp[i] <= w:
            print(i)
            return

main()

Submission status: Runtime Error

Solution code:
def main():

    n, w = map(int, input().split())

    INF = 10 * 20
    dp = [INF] * (n * 1000)
    dp[0] = 0

    max_vi = 0
    for _ in range(n):
        wi, vi = map(int, input().split())
        max_vi += vi

        for vj in range(max_vi + 1, vi - 1, -1):
            nw = dp[vj - vi] + wi
            if dp[vj] > nw:
                dp[vj] = nw

    for i in range(max_vi, -1, -1):
        if dp[i] <= w:
            print(i)
            return

main()

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
import copy
input = sys.stdin.readline
INF = int(float("inf"))
N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    tempW, tempV = map(int, input().split())
    weight.append(tempW)
    value.append(tempV)

dp = [[INF for _ in range(N * 1000 + 1)] for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    for l in range(N * 1000 + 1):
        if l - value[i - 1] >= 0:
            dp[i][l] = min(dp[i - 1][l], dp[i - 1][l - value[i - 1]] + weight[i - 1])
        else:
            dp[i][l] = dp[i - 1][l]
for i in range(N * 1000 + 1):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
import copy

INF = 10 ** 9 + 7
N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    tempW, tempV = map(int, input().split())
    weight.append(tempW)
    value.append(tempV)

dp = [[INF for _ in range(N * 300)] for _ in range(N)]
for i in range(value[0]):
    dp[0][i] = weight[0]

for i in range(N):
    for l in range(N * 300):
        if l - value[i] >= 0:
            dp[i][l] = min(dp[i - 1][l], dp[i - 1][l - value[i]] + weight[i])
        else:
            dp[i][l] = min(weight[i], dp[i - 1][l])
for i in range(N * 300 - 1):
    if dp[-1][i] <= W < dp[-1][i + 1]:
        print(i + 1)
        break
    elif i == N * 300 - 2:
        print(N * 300)

Submission status: Runtime Error

Solution code:
INF = 10 ** 9 + 7
N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    tempW, tempV = map(int, input().split())
    weight.append(tempW)
    value.append(tempV)

dp = [[INF for _ in range(N * 300)] for _ in range(N)]
for i in range(value[0]):
    dp[0][i] = weight[0]

for i in range(N):
    for l in range(N * 300):
        if l - value[i] >= 0:
            dp[i][l] = min(dp[i - 1][l], dp[i - 1][l - value[i]] + weight[i])
        else:
            dp[i][l] = min(weight[i], dp[i - 1][l])
for i in range(N * 300 - 1):
    if dp[-1][i] <= W < dp[-1][i + 1]:
        print(i + 1)
        break
    elif i == N * 300 - 2:
        print(N * 300)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
import copy

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 9 + 7
dp = [[INF for _ in range(N * 300)] for _ in range(N)]

for i in range(wv[0][1]):
    dp[0][i] = wv[0][0]
for i in range(1, N):
    for l in range(N * 300):
        if l - wv[i - 1][1] >= 0:
            dp[i][l] = min(dp[i - 1][l], dp[i - 1][l - wv[i][1]] + wv[i][0])
        else:
            dp[i][l] = min(dp[i - 1][l], wv[i][0])
for i in range(N * 300 - 1):
    if dp[-1][i] <= W < dp[-1][i + 1]:
        print(i+1)
        break

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
import copy

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 9 + 7
dp = [[INF for _ in range(N * 300 + 1)] for _ in range(N + 1)]

for i in dp:
    i[0] = 0
for i in range(1, wv[0][1] + 1):
    dp[1][i] = wv[0][0]

for i in range(2, N + 1):
    for l in range(1, N * 300 + 1):
        if l - wv[i - 1][1] >= 0:
            dp[i][l] = min(dp[i - 1][l], dp[i - 1][l - wv[i - 1][1]] + wv[i - 1][0])
        elif dp[i][l] == 10 ** 9 + 7:
            dp[i][l] = min(wv[i - 1][0], dp[i - 1][l])
        else:
            dp[i][l] = dp[i - 1][l]
for i in range(N * 300):
    if dp[-1][i] <= W < dp[-1][i + 1]:
        print(i)
        break
    elif i == N*300-1:
        print(i+1)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
import copy

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 9 + 7
dp = [[INF for _ in range(N * 300 + 1)] for _ in range(N + 1)]

for i in dp:
    i[0] = 0
for i in range(1, wv[0][1] + 1):
    dp[1][i] = wv[0][0]

for i in range(2, N + 1):
    for l in range(1, N * 300 + 1):
        if l - wv[i - 1][1] >= 0:
            dp[i][l] = min(dp[i - 1][l], dp[i - 1][l - wv[i - 1][1]] + wv[i - 1][0])
        elif dp[i][l] == 10 ** 9 + 7:
            dp[i][l] = min(wv[i - 1][0], dp[i - 1][l])
        else:
            dp[i][l] = dp[i - 1][l]
for i in range(N * 300):
    if dp[-1][i] <= W < dp[-1][i + 1]:
        print(i)
        break
    elif i == N*300-1:
        print(i)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
import copy

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 9 + 7
dp = [[INF for _ in range(N * 300 + 1)] for _ in range(N + 1)]

for i in dp:
    i[0] = 0
for i in range(1, wv[0][1]+1):
    dp[1][i] = wv[0][0]

for i in range(2, N + 1):
    for l in range(1, N * 300 + 1):
        if l - wv[i - 1][1] >= 0:
            dp[i][l] = min(dp[i - 1][l], dp[i - 1][l - wv[i - 1][1]] + wv[i - 1][0])
        elif dp[i][l] == 10**9+7:
            dp[i][l] = min(wv[i-1][0], dp[i-1][l])
        else:
            dp[i][l] = dp[i - 1][l]
for i in range(N*300+1):
    if dp[-1][i] <= W < dp[-1][i+1]:
        print(i)
        break

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
import copy

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 9 + 7
dp = [[INF for _ in range(N * 300 + 1)] for _ in range(N + 1)]

for i in dp:
    i[0] = 0
for i in range(1, wv[0][1]+1):
    dp[1][i] = wv[0][0]

for i in range(2, N + 1):
    for l in range(1, N * 300 + 1):
        if l - wv[i - 1][1] >= 0:
            dp[i][l] = min(dp[i - 1][l], dp[i - 1][l - wv[i - 1][1]] + wv[i - 1][0])
        elif dp[i][l] == 10**9+7:
            dp[i][l] = min(wv[i-1][0], dp[i-1][l])
        else:
            dp[i][l] = dp[i - 1][l]
for i, l in enumerate(dp[-1]):
    if l <= W < dp[-1][i + 1]:
        print(i)
        break

Submission status: Runtime Error

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

def main3():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = [0]*(W+1)

    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for w, v in wv:
        for i in range(W, w-1, -1):
            tmp = dp[i-w] + v
            if dp[i] < tmp:
                dp[i] = tmp
        #print(dp,sep="\n")

    #4:出力
    print(max(dp))

if __name__ == '__main__':
    main3()

Submission status: Runtime Error

Solution code:
"""memo
    numpyでやるときは配列を一気に更新するが(numpy使いたくないのでやらない)，
    このやり方は後ろの方から更新することで後の更新に影響を与えない(考え方すごい)．
    (参考#9889377)
"""

import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = map(int,input().split())
    dp = [0]*(W+1)

    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = map(int,input().split())
        for i in range(W, w-1, -1):
            tmp = dp[i-w] + v
            if dp[i] < tmp:
                dp[i] = tmp
        #print(dp,sep="\n")

    #4:出力
    print(max(dp))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

N, W = map(int, input().split())
wv = []
#i番目までを詰めたときの最大の価値を記録
dp = np.zeros(W+1)
for i in range(N):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[:-w]+v, dp[w:])

print(int(dp[-1]))

Submission status: Runtime Error

Solution code:
import numpy as np

N, W = map(int, input().split())
wv = []
for i in range(N):
    w, v = map(int, input().split())
    wv.append([w,v])

#i番目までを使ってjの重さで入れたときの価値の最大値を記録する
dp = np.zeros((N+1,W+1))
for j in range(1,W+1):
    for i in range(1,N+1):
        if j < wv[i-1][0]:
            dp[i,j] = dp[i-1,j]
        else:
            dp[i,j] = max(dp[i-1,j-wv[i-1][0]] + wv[i-1][1], dp[i-1,j])
print(int(dp[-1][-1]))

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
#0 weight , [1] value
table = [list(map(int, input().split())) for _ in range(n)]

'''
w = 10^9
要素が多すぎる？
'''
wmax = 0
vmax = 0
for i in table:
    wmax += i[0]
    vmax += i[1]

if w >= wmax:
    print(vmax)
    exit()

else:
    #print("お腹いっぱい")
    dp = [[0] * (w+1) for i in range(n+1)]

    def choice_max(a, b):
        if a > b:
            return a
        else:
            return b

    for i in range(n):
        for j in range(w+1):
            if(j >= table[i][0]):
                dp[i+1][j] = choice_max(
                                dp[i][j],
                                dp[i][j - table[i][0]] + table[i][1]
                                )
            else:
                dp[i+1][j] = dp[i][j]
    #[print(item)for item in dp]
    print(dp[n][w])

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
#0 weight , [1] value
table = [list(map(int, input().split())) for _ in range(n)]

'''
w = 10^9
要素が多すぎる？
'''
wmax = 0
for i in table:
    wmax += i[0]

if w >= wmax:
    print(wmax)
    exit()

else:
    #print("お腹いっぱい")
    dp = [[0] * (w+1) for i in range(n+1)]

    def choice_max(a, b):
        if a > b:
            return a
        else:
            return b

    for i in range(n):
        for j in range(w+1):
            if(j >= table[i][0]):
                dp[i+1][j] = choice_max(
                                dp[i][j],
                                dp[i][j - table[i][0]] + table[i][1]
                                )
            else:
                dp[i+1][j] = dp[i][j]
    #[print(item)for item in dp]
    print(dp[n][w])

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
#0 weight , [1] value
table = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w+1) for i in range(n+1)]

def choice_max(a, b):
    if a > b:
        return a
    else:
        return b

for i in range(n):
    for j in range(w+1):
        if(j >= table[i][0]):
            dp[i+1][j] = choice_max(
                            dp[i][j],
                            dp[i][j - table[i][0]] + table[i][1]
                            )
        else:
            dp[i+1][j] = dp[i][j]
#[print(item)for item in dp]
print(dp[n][w])

Submission status: Runtime Error

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

dp = [0]*(w+1)

for _ in range(n):
  wei, v = map(int, input().split())
  dp_1 = dp[:]
  for j in range(w + 1):
    if j - wei >= 0:
      dp[j] = dp_1[j-wei] + v if (dp_1[j-wei] + v) > dp_1[j] else dp[j]
  
print(dp[w])

Submission status: Runtime Error

Solution code:
n,W=map(int,input().split())
lst=[]
for i in range(n):
  w,v=map(int,input().split())
  lst.append([w,v])
nap=[]
for i in range(n+1):
  nap.append([0]*(W+1))
for i in range(1,n+1):
  for j in range(1,W+1):
    if lst[i-1][0]<=j:
      nap[i][j]=max(nap[i-1][j],nap[i-1][j-lst[i-1][0]]+lst[i-1][1])
    else:
      nap[i][j]=nap[i-1][j]
print(nap[n][W])

Submission status: Runtime Error

Solution code:
# 1つづつ順に
def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

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

    for i in range(N):
        for j in range(W+1):
            w = w_v[i][0]
            v = w_v[i][1]
            if j < w:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j], dp[i][j - w] + v)
 
    print(dp[N][W])
if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
# 1つづつ順に
def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

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

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

# 遷移先を考えて移動。初期化は0
def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

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

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


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

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


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    maxv=sum(v)+1
    dp=[[2**60]*maxv for _ in range(N+1)]
    dp[0][0]=0
    for i in range(N):
        for j in range(maxv):
            if j>=v[i]:
                dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
            else:                                                                                                                                            empla
                dp[i+1][j]=dp[i][j]                                                                                                                          te)

    ans=0
    for j in range(maxv):
        if W >= dp[N][j]:
            ans=j                                                                                                                                            empla
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int                                                                                                                       empla
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"                                                                                                                   15292
    for i in range(N):                                                                                                                                       46976
        w[i] = int(next(tokens))                                                                                                                             04606
        v[i] = int(next(tokens))                                                                                                                             52921
    solve(N, W, w, v)                                                                                                                                        76, 1
                                                                                                                                                             46068
if __name__ == '__main__':                                                                                                                                   29215
    main()

Submission status: Runtime Error

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

def main():
    n, W = map(int, input().split())
    dp = np.zeros(W + 1, dtype = np.int64)
    for i in range(n):
        w,v=map(int,input().split())
        dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
    print(max(dp))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
	for j in range(W + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
		# 品物(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:
import numpy as np
n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

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

for i in range(n):
    dp[i+1][:wv[i][0]] = dp[i][:wv[i][0]]
    dp[i+1][wv[i][0]:] = np.maximum(dp[i][:-wv[i][0]] + wv[i][1], dp[i][wv[i][0]:])
print(dp[n][W])

Submission status: Runtime Error

Solution code:
N, W = [int(i) for i in input().rstrip().split()]
F = [[int(i) for i in input().rstrip().split()] for _ in range(N)]
V = sum([v for w,v in F])
def dp2(f,v):
    global F
    if v < 0:
        return 10 ** 10
    if f == 0:
        if v == 0:
            return 0
        elif v > F[0][1]:
            return 10 ** 10
        else:
            return F[0][0]
    return min(dp(f - 1, v), dp(f - 1, v - F[f][1]) + F[f][0])

for v in range(V):
    if dp2(N-1,v) == W:
        print(v)
        break

Submission status: Runtime Error

Solution code:
N,W = [int(i) for i in input().rstrip().split()]
F = [[int(i) for i in input().rstrip().split()] for _ in range(N)]

DP = []
for w,v in F:
    if DP == []:
        DP = [0]*w+[v]*(W-w+1)
    else:
        dp = DP[::]
        for w2 in range(w,W+1):
            dp[w2] = max(DP[w2-w] + v, DP[w2])
        DP = dp
    #print(DP)
print(DP[-1])

Submission status: Runtime Error

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

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

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

print(max(dp[-1]))

Submission status: Runtime Error

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

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

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

print(max(dp[-1]))

Submission status: Runtime Error

Solution code:
#PythonだとTLE、PyPyだとAC
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)
inf=float("inf")
dp = [[inf for i in range(V)] for j in range(N)]

for i in range(N):
    for j in range(v[i]):
        dp[i][j] = w[i]

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

print(dp[-1].index(W+1))

Submission status: Runtime Error

Solution code:
N, W = list(map(int, input().split()))
WE = []
V = []
for i in range(N):
    w, v = list(map(int, input().split()))
    WE.append(w)
    V.append(v)

# MAX_W = 10 ** 5
MAX_W = 10 ** 9

# DP[i][j]: i以降の品物で重さj以下のときの価値の最大
DP = []
for i in range(N):
    a = [None] * (MAX_W + 1)
    DP.append(a)
DP.append([0] * (MAX_W+1))

for i in range(N-1, -1, -1):
    for j in range(MAX_W+1):
        if i == N:  # i番目の品物はない
            DP[i][j] == 0
        elif j < WE[i]:  # この重さの品物は入れないから無視
            DP[i][j] = DP[i+1][j]
        else:
            DP[i][j] = max(DP[i+1][j], DP[i+1][j-WE[i]]+V[i])

# for i in range(N):
#     print(DP[i][:10])
print(DP[0][W])

Submission status: Runtime Error

Solution code:
N, W = list(map(int, input().split()))
WE = []
V = []
for i in range(N):
    w, v = list(map(int, input().split()))
    WE.append(w)
    V.append(v)

# MAX_W = 10 ** 5
MAX_W = 10 ** ９

# DP[i][j]: i以降の品物で重さj以下のときの価値の最大
DP = []
for i in range(N):
    a = [None] * (MAX_W + 1)
    DP.append(a)
DP.append([0] * (MAX_W+1))

for i in range(N-1, -1, -1):
    for j in range(MAX_W+1):
        if i == N:  # i番目の品物はない
            DP[i][j] == 0
        elif j < WE[i]:  # この重さの品物は入れないから無視
            DP[i][j] = DP[i+1][j]
        else:
            DP[i][j] = max(DP[i+1][j], DP[i+1][j-WE[i]]+V[i])

# for i in range(N):
#     print(DP[i][:10])
print(DP[0][W])

Submission status: Runtime Error

Solution code:
N, W = list(map(int, input().split()))
WE = []
V = []
for i in range(N):
    w, v = list(map(int, input().split()))
    WE.append(w)
    V.append(v)

MAX_W = 10 ** 5

# DP[i][j]: i以降の品物で重さj以下のときの価値の最大
DP = []
for i in range(N):
    a = [None] * (MAX_W + 1)
    DP.append(a)
DP.append([0] * (MAX_W+1))

for i in range(N-1, -1, -1):
    for j in range(MAX_W+1):
        if i == N:  # i番目の品物はない
            DP[i][j] == 0
        elif j < WE[i]:  # この重さの品物は入れないから無視
            DP[i][j] = DP[i+1][j]
        else:
            DP[i][j] = max(DP[i+1][j], DP[i+1][j-WE[i]]+V[i])

# for i in range(N):
#     print(DP[i][:10])
print(DP[0][W])