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 sys
input = sys.stdin.readline

def main():
  
  def knapsack_price(single=True):
    V = sum(price_list)
    dp_max = W + 1
    dp = [dp_max] * (V-1)
    dp[0] = 0
    
    for item in range(N):
      if single:
        S = reversed(range(price_list[item], V+1))
      else:
        S = range(price_list[item], V+1)
      
      for price in S:
        dp[price] = min(dp[price], dp[price - price_list[item]] + weight_lsit[item])
    return max(price for price in range(V+1) if dp[price] <= W)
  
  N,W = map(int,input().split())
  
  price_list = []
  weight_list = []
  for _ in range(N):
    weight, price = map(int,input().split())
    price_list.append(price)
    weight_list.append(weight)
    
  print(knapsack_price(single=True)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
N, W = map(int, input().rstrip().split(' '))
weight_array = np.zeros(W+1, dtype=np.uint64)

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

Submission status: Runtime Error

Solution code:
import numpy as np
N, W = map(int, input().rstrip().split(' '))
weight_array = np.zeros(W+1)

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

Submission status: Runtime Error

Solution code:
import numba as nb
import sys
import numpy as np
@nb.njit
def solve(w,weight,value):
    total=w
    dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
    for i in range(l):
        for w in range(total+1):
            if weight[i]<=w:
                dp[i][w]=max(value[i]+dp[i-1][w-weight[i]],dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    print(dp[l-1][total])
n,w=map(int,sys.stdin.readline().split())
weight=[0]*n
value=[0]*n
total=w
for i in range(n):
    x,y=map(int,sys.stdin.readline().split())
    weight[i]=x
    value[i]=y
l=len(weight)
solve(w,weight,value)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
import sys

n, k = list(map(int, input().split()))
stones = list(map(int, input().split()))

dp = [sys.maxsize] * n
dp[0] = 0
for i in range(n):
    for j in range(i + 1, i + k + 1):
        if j < n:
            dp[j] = min(dp[j], dp[i] + abs(stones[i] - stones[j]))
print(dp[n - 1], end="")

Submission status: Runtime Error

Solution code:
### https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))

dp={0:0}
for i in range(N):
    Current_Weight,Current_Value = map(int,input().split())
    if (i == 0) & (Current_Weight <= W) :
        dp[Current_Weight] = Current_Value
    elif i > 0:
        Last_Search_List = list(dp.keys())
        Current_Search_List = list(map(lambda x:x+Current_Weight,Last_Search_List))
        for j in range(len(Current_Search_List)):
            Last_Search_Weight = Last_Search_List[j]
            Current_Search_Weight = Current_Search_List[j]
            if Current_Search_Weight in dp:
                dp[Current_Search_Weight] = max(dp[Current_Search_Weight],
                                                dp[Last_Search_Weight] + Current_Value)
            elif Current_Search_Weight <= W :
                dp[Current_Search_Weight] = dp[Last_Search_Weight] + Current_Value

print(max(dp.values()))

Submission status: Runtime Error

Solution code:
INF = 10**9 + 7


def main():
    N, W = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(N)]

    dp = [[INF]*(10**4+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(10**4 + 1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if 0 <= j - A[i][1] and dp[i][j - A[i][1]] + A[i][0] <= W:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j - A[i][1]] + A[i][0])
    ans = 0
    for j in range(10**4+1)[::-1]:
        if dp[N][j] <= W:
            ans = break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))
 
Sum_Weight = sum(map(lambda x:x[0],Goods_List))
dp = [[-1] * (W + 1) for i in range(N)]
 
for i in range(N):
    Current_Weight = Goods_List[i][0]
    Current_Value  = Goods_List[i][1]
    dp[i][0] = 0
    if (i == 0) & (Current_Weight <= W) :
        dp[i][Current_Weight] = Current_Value
    elif i > 0:
        Last_Search_List = [j for j, x in enumerate(dp[i-1]) if x > -1]
        Current_Search_List = list(map(lambda x:x+Current_Weight,Last_Search_List))
        ##まずは前回値を入れる
        for l in range(len(Last_Search_List)):
            Last_Search_Weight =  Last_Search_List[l] 
            dp[i][Last_Search_Weight] = dp[i-1][Last_Search_Weight]
        ##今回値と比べる
        for k in range(len(Current_Search_List)):
            Last_Search_Weight =  Last_Search_List[k] 
            Current_Search_Weight = Current_Search_List[k]
            if Current_Search_Weight > W:
                break
            else:
                dp[i][Current_Search_Weight] = max((dp[i-1][Last_Search_Weight] + Current_Value),
                                                   dp[i-1][Current_Search_Weight])
 
 
print(max(dp[N-1]))

Submission status: Runtime Error

Solution code:
import numpy as np

N, W = [int(x) for x in input().split()]
items = [tuple(map(int, input().split())) for _ in range(N)]

#topdown
memo = np.zeros(shape = W+1, dtype = np.int64)

for w,v in items:
    memo[w:] = np.maximum( memo[w:], memo[:-w] + v)

print(memo[-1])

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
L=[]
for _ in range(N):
    w,v=map(int,input().split())
    L.append([w,v])

DP=[[0]*(W+1) for _ in range(N+1)]
for j in range(1,N+1):
    if L[j-1][0]<=W:
        for k in range(L[j-1][0],W+1):
            DP[j][k]=max(DP[j-1][k],DP[j-1][k-L[j-1][0]]+L[j-1][1])
        for l in range(L[j-1][0]):
            DP[j][l]=DP[j-1][l]
    else:
        for m in range(0,W+1):
            DP[j][m]=DP[j-1][m]
            
print(DP[N][W])

Submission status: Runtime Error

Solution code:
IN=lambda:map(int,input().split())
N,W=IN()
INF=float("inf")
dp=[INF]*(100*N)
dp.insert(0,0)
c=0
ans=0
for i in range(N):
    w,v=IN()
    for j in range((100*N+1),-1,-1):
        if dp[j-v]!=INF:
            dp[j]=min(dp[j],dp[j-v]+w)
for i in dp:
    c+=1
    if i<=W:
        ans=c-1
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def solve(a,w,dp):
    if not a or w==0: return 0
    if (str(a),w) in dp: return dp[(str(a),w)]
    maxx=0
    for i in range(len(a)):
        if a[i][0]<=w:
            maxx=max(maxx,a[i][1]+solve(a[:i]+a[i+1:],w-a[i][0],dp))
    dp[(str(a),w)]=maxx
    return maxx
if __name__=='__main__':
    n,w=map(int,input().split())
    a=[]
    sw=0
    for i in range(n):
        p,q=map(int,input().split())
        a.append((p,q))
        sw+=a[-1][0]
    a.sort(key=lambda x: x[0])
    print(solve(a,w,{}))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
 
table = [[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 - wv[i-1][0] >= 0):
      table[i][j] = max(table[i-1][j], table[i-1][j - wv[i-1][0]] + wv[i-1][1])
    else:
      table[i][j] = table[i-1][j]
 
print(table[N][W])

Submission status: Runtime Error

Solution code:
import sys
#import numpy as np
#from collections import defaultdict
import math
#from collections import deque

input = sys.stdin.readline
#import numpy as np



def main():

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

    dp = [0] * (W+2)

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

        for j in range(W+1,w-1,-1):
            dp[j] =max(dp[j-w] +v ,dp[j])

    print(dp[W])
#    print(dp)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

def knapsack(sm,W,n,V):
    K = [0]*(sm+1)
    for i in range(1,n+1):
        for j in reversed(range(1,sm+1)):
            if j - W[i-1] >= 0:
                K[j] = max(V[i-1]+K[j-W[i-1]], K[j])
    return K[-1]

n,wt = ip()
V,W = [0]*n,[0]*n
for i in range(n):
    w,v = ip()
    V[i] = v
    W[i] = w
ans = knapsack(wt,W,n,V)
print(ans)

Submission status: Runtime Error

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

def knapsack(sm,W,n,V):
    K = [[0]*(sm+1) for i in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,sm+1):
            K[i][j] = K[i-1][j]
            if W[i-1] <= j:
                K[i][j] = max(V[i-1]+K[i-1][j-W[i-1]], K[i-1][j])
    return K[n][sm]

n,wt = ip()
V,W = [0]*n,[0]*n
for i in range(n):
    w,v = ip()
    V[i] = v
    W[i] = w

ans = knapsack(wt,W,n,V)
print(ans)

Submission status: Runtime Error

Solution code:

import numpy as np
n, W = map(int,input().split())
w = []
v = []
for i in range(n):
    w_,v_= map(int,input().split())
    w.append(w_)
    v.append(v_)
dp = np.zeros(W+1, dtype=np.int128)
for i in range(n):
	dp[w[i]:] = np.maximum(dp[:-w[i]] + v[i], dp[w[i]:])
print(dp[W])

Submission status: Runtime Error

Solution code:

import numpy as np
n, W = map(int,input().split())
w = []
v = []
for i in range(n):
    w_,v_= map(int,input().split())
    w.append(w_)
    v.append(v_)
dp = np.zeros(W+1, dtype=np.int64)
for i in range(n):
	dp[w[i]:] = np.maximum(dp[:-w[i]] + v[i], dp[w[i]:])
print(dp[W])

Submission status: Runtime Error

Solution code:
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
dp=[0]*(b+1)
for i in range(a):
  x,y=mi()
  for i in range(b-x,-1,-1):
      dp[i+x]=max(dp[i]+y,dp[i+x])
print(max(dp))

Submission status: Runtime Error

Solution code:
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
import numpy as np
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
dp=[0]*(b+1)
for i in range(a):
  x,y=mi()
  for i in range(b-x,-1,-1):
      dp[i+x]=max(dp[i]+y,dp[i+x])
print(max(dp))

Submission status: Runtime Error

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

li = [list(map(int,input().split())) for i in range(N)]

dp = [[0]*(W+1) for i in range(N)]
#dp[i][w] indexi 番目まででwになるような価値の最大値

w = li[0][0]
if w<=W:
    dp[0][w]= li[0][1]

for i in range(N-1):
    wi =  li[i+1][0]
    for w in range(W+1):
        if w>=wi:
            dp[i+1][w] = max(dp[i][w],dp[i][w-wi]+li[i+1][1])
        else:
            dp[i+1][w] = dp[i][w]

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

Submission status: Runtime Error

Solution code:
n,w=[int(x) for x in input().split()]
dp=[0]*(w+1)
lw=w
for test in range(n):
    cw, v = [int(x) for x in input().split()]
    temp=[0]*(w+1)
    for i in range(1,w+1):
        if cw <= i :
            temp[i]=max(dp[i],v+dp[i-cw])
        else:
            temp[i]=max(dp[i],temp[i-1])
    dp=temp[:]
    #print(dp)
print(dp[w])

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
import sys
sys.setrecursionlimit(10**19)
W=[0]*n
V=[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(1,n+1):
  for j in range(1,w+1):
    if j-W[i-1]>=0:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-W[i-1]]+V[i-1])
    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=[0]*n
V=[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(1,n+1):
  for j in range(1,w+1):
    if j-W[i-1]>=0:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-W[i-1]]+V[i-1])
    else:
      dp[i][j]=dp[i-1][j]
print(dp[n][w])

Submission status: Runtime Error

Solution code:
import numpy as np

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

Submission status: Runtime Error

Solution code:
n, w = map(int,input().split())
weight = []
value = []
for i in range(n):
    x, y = map(int,input().split())
    weight.append(x)
    value.append(y)

dp = [[0]*(w+1) for i in range(n+1)]
# dp[i][sum_w] := i-1 番目までの品物から重さが sum_w を超えないように選んだときの、価値の総和の最大値
omosa = 0

for i in range(n):
    for omosa in range(w+1):
        if weight[i] <= omosa: #もし追加しても制限を超えないなら
            #i番目の商品を選ぶ場合
            dp[i+1][omosa] = max(dp[i+1][omosa], value[i] + dp[i][omosa-weight[i]])
        #i番目の商品を選ばない場合(これはいつでも起きる)
        dp[i+1][omosa] = max(dp[i+1][omosa], dp[i][omosa])

print(dp[n][w])

Submission status: Runtime Error

Solution code:
# AC by Pypy not Python
# Pythonで通すためには,  npで配列毎まるっと処理する必要あり

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

dp = [0] * (W+1) # DP枠_重さ’0’～'W'まで準備

for i in range(N):
    w, v = map(int, input().split()) # 商品, 各々重さと価値
    tmp = dp[:] # ひとつ前の商品までのDP枠を参照用にコピー
    for j in range(1, W+1): # 各商品のDP枠への落とし込み
        if j  >= w and tmp[j] < tmp[j-w] + v: # 商品の重さよりDP枠の重さが重い場合で...
            dp[j] = tmp[j-w] + v # この商品を加え, 合計価値が up する場合は replace
        else: # 商品の重さよりDP枠の重さが軽い場合と, ↑で価値が up しない場合は...
            dp[j] = tmp[j] # ↑ 参照データをそのままコピー
    
print(dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
def resolve():
	# N: 品物の個数、W: 容量の上限
	N, W = map(int, input().split())
	# DP配列の宣言: あるナップサック内の体積における価値の最大値
	dp = np.zeros(W+1, dtype=np.int64)
	# 商品数繰り返す
	for _ in range(N):
		# 各商品の重さwと価値vを読み込み
		w, v = map(int, input().split())
		# 商品の重さ以上のテーブルを価値の最大値に更新
		dp[w:] = np.maximum(
			# 入れない時（そのまま）と
			dp[w:],
			# 入れた時（入れる前の価値＋この商品の価値）
			dp[:W+1-w] + v
		)
	print(dp[W])
resolve()

Submission status: Runtime Error

Solution code:
def resolve():
	# N: 品物の個数、W: 容量の上限
	N, W = map(int, input().split())
	# DP配列の宣言: あるナップサック内の体積における価値の最大値
	dp = np.zeros(W+1, dtype=np.int64)
	# 商品数繰り返す
	for _ in range(N):
		# 各商品の重さwと価値vを読み込み
		w, v = map(int, input().split())
		# 商品の重さ以上のテーブルを価値の最大値に更新
		dp[w:] = np.maximum(
			# 入れない時（そのまま）と
			dp[w:],
			# 入れた時（入れる前の価値＋この商品の価値）
			dp[:W+1-w] + v
		)
	print(dp[W])
resolve()

Submission status: Runtime Error

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

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

for j in range(m+1):
        if dp[N][j] <= W:
            ans = max(ans,j)
print(ans)

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
MAX_V = 10**5+1
dp = [float('inf')] * MAX_V
dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for sum_v in range(MAX_V)[::-1]:
        if sum_v >= v:
            dp[sum_v] = min(dp[sum_v - v] + w, dp[sum_v])
        else:
            dp[sum_v] = min(dp[sum_v], w)
ans = 0
while dp[ans+1] <= W:
    ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
MAX_V = 10**5
dp = [[10**18]*(MAX_V+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(1,n+1):
    w, v = map(int, input().split())
    for sum_v in range(MAX_V+1):
        if sum_v >= v:
            dp[i][sum_v] = min(dp[i-1][sum_v], dp[i-1][sum_v - v] + w)
        else:
            dp[i][sum_v] = min(dp[i-1][sum_v], w)

ans = 0
last_dp = dp[n]
while last_dp[ans+1] <= W:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
MAX_V = 10**5
dp = [10**18]*(MAX_V+1)
dp[0] = 0
tmp_dp = [0]*(MAX_V+1)
for _ in range(n):
    w, v = map(int, input().split())
    for sum_v in range(MAX_V+1):
        if sum_v >= v:
            tmp_dp[sum_v] = min(dp[sum_v], dp[sum_v - v] + w)
        else:
            tmp_dp[sum_v] = min(dp[sum_v], w)
    dp = tmp_dp
    tmp_dp = [0]*(MAX_V+1)

ans = 0
while dp[ans+1] <= W:
    ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
MAX_V = 100000
dp = [0] + [10**18]*MAX_V
tmp_dp = [0]*(MAX_V+1)
for _ in range(n):
    w, v = map(int, input().split())
    for sum_v in range(MAX_V+1):
        if sum_v >= v:
            tmp_dp[sum_v] = min(dp[sum_v], dp[sum_v - v] + w)
        else:
            tmp_dp[sum_v] = min(dp[sum_v], w)
    dp = tmp_dp
    tmp_dp = [0]*(MAX_V+1)

ans = 0
while dp[ans+1] <= W:
    ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
MAX_V = 100100
dp = [0] + [10**18]*MAX_V
for _ in range(n):
    w, v = map(int, input().split())
    for sum_v in range(MAX_V+1):
        if sum_v >= v:
            tmp_dp[sum_v] = min(dp[sum_v], dp[sum_v - v] + w)
        else:
            tmp_dp[sum_v] = min(dp[sum_v], w)
    dp = tmp_dp
    tmp_dp = [0]*(MAX_V+1)

ans = 0
while dp[ans+1] <= W:
    ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
MAX_V = 100000
dp = [0] + [float('INF')]*MAX_V
for _ in range(n):
    tmp_dp = [0]*(MAX_V+1)
    w, v = map(int, input().split())
    for sum_v in range(MAX_V+1):
        if sum_v >= v:
            tmp_dp[sum_v] = min(dp[sum_v], dp[sum_v - v] + w)
        else:
            tmp_dp[sum_v] = min(dp[sum_v], w)
    dp = tmp_dp

ans = 0
while dp[ans+1] <= W:
    ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
MAX_V = 100000
dp = [0] + [10**(18)]*MAX_V
for _ in range(n):
    tmp_dp = [0]*(MAX_V+1)
    w, v = map(int, input().split())
    for sum_v in range(MAX_V+1):
        if sum_v >= v:
            tmp_dp[sum_v] = min(dp[sum_v], dp[sum_v - v] + w)
        else:
            tmp_dp[sum_v] = min(dp[sum_v], w)
    dp = tmp_dp

ans = 0
while dp[ans+1] <= W:
    ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
MAX_V = 10000
dp = [0] + [10**(18)]*MAX_V
for _ in range(n):
    tmp_dp = [0]*(MAX_V+1)
    w, v = map(int, input().split())
    for sum_v in range(MAX_V+1):
        if sum_v >= v:
            tmp_dp[sum_v] = min(dp[sum_v], dp[sum_v - v] + w)
        else:
            tmp_dp[sum_v] = min(dp[sum_v], w)
    dp = tmp_dp

ans = 0
while dp[ans+1] <= W:
    ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
MAX_V = 1000
dp = [0] + [10**(18)]*MAX_V
for _ in range(n):
    tmp_dp = [0]*(MAX_V+1)
    w, v = map(int, input().split())
    for sum_v in range(MAX_V+1):
        if sum_v >= v:
            tmp_dp[sum_v] = min(dp[sum_v], dp[sum_v - v] + w)
        else:
            tmp_dp[sum_v] = min(dp[sum_v], w)
    dp = tmp_dp

ans = 0
while dp[ans+1] <= W:
    ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
MAX_V = 1000
dp = [0] + [float('INF')]*MAX_V
for _ in range(n):
    tmp_dp = [0]*(MAX_V+1)
    w, v = map(int, input().split())
    for sum_v in range(MAX_V+1):
        if sum_v >= v:
            tmp_dp[sum_v] = min(dp[sum_v], dp[sum_v - v] + w)
        else:
            tmp_dp[sum_v] = min(dp[sum_v], w)
    dp = tmp_dp

ans = 0
while dp[ans+1] <= W:
    ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
MAX_V = 1000
dp = [0] + [float('INF')]*MAX_V
for _ in range(n):
    w, v = map(int, input().split())
    tmp_dp = [min(dp[sum_v], dp[sum_v - v] + w) if sum_v >= v else min(dp[sum_v], w) for sum_v in range(MAX_V) ]
    dp = tmp_dp

ans = 0
while dp[ans+1] <= W:
    ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
MAX_V = 1000
dp = [0] + [float('INF')]*MAX_V
for _ in range(n):
    w, v = map(int, input().split())
    tmp_dp = [min(dp[sum_v], dp[sum_v - v] + w) if sum_v >= v else min(dp[sum_v], w) for sum_v in range(MAX_V) ]
    dp = tmp_dp

ans = 0
while dp[ans+1] <= W:
    ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
n,w = map(int,input().split())
inf = float("inf")
dp = [[-inf]*(w+1) for _ in range(n+1)]
for j in range(w+1):
    dp[0][j] = 0
for i in range(n):
    s,t = map(int,input().split())
    for l in range(w+1):
        if l-s >=0:
            dp[i+1][l] = max(dp[i][l],dp[i][l-s]+t)
        else:
            dp[i+1][l] = dp[i][l]
print(dp[-1][w])

Submission status: Runtime Error

Solution code:
def e():
    import numpy as np

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

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

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

    print(dp[-1])


##########
if __name__ == "__main__":
    e()

Submission status: Runtime Error

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

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

#f_inf = float("inf")
#dp = [f_inf]*N

# dp[i][w] = "番号 i 以下の商品でバッグの重さが w 以下になるように最適に詰めた場合"
dp = np.array([[0]*(W+1)]*(N+1),dtype=np.int64)

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

for i in range(1,N+1):
    for w in range(wv[i-1,0],W+1):
        dp[i,w] = max(dp[i-1,w-wv[i-1,0]]+wv[i-1,1] , dp[i-1,w])
    dp[i,1:wv[i-1,0]] = dp[i-1,1:wv[i-1,0]]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
def e():
    import numpy as np
 
    N, W = map(int, input().split())
 
    dp = np.zeros(W+1, dtype=np.int64)
 
    for _ in range(N):
        w, v = map(int, input().split())
        np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])
 
    print(dp[-1])
 
 
##########
if __name__ == "__main__":
    e()

Submission status: Runtime Error

Solution code:
def e():
    import numpy as np

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

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

    for _ in range(N):
        w, v = map(int, input().split())
        # print('_, dp[:-w]+v, dp[w:], out=dp[w:] = {}, {}, {}, {}'.format(_, dp[:-w]+v, dp[w:], dp[w:]))
        np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

    print(dp[-1])


##########
if __name__ == "__main__":
    e()

Submission status: Runtime Error

Solution code:
# はやい
def e():
    import numpy as np

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

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

    for _ in range(N):
        w, v = map(int, input().split())
        print('_, dp[:-w]+v, dp[w:], out=dp[w:] = {}, {}, {}, {}'.format(_,
                                                                         dp[:-w]+v, dp[w:], dp[w:]))
        np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

    print(dp[-1])


##########
if __name__ == "__main__":
    e()

Submission status: Runtime Error

Solution code:
n,w = map(int, input().split())
high = [0] * (w + 1)
for i in range(n):
    weight, value = map(int, input().split())
    if weight <= w:
        renewal = high[:weight]
        renewal += [max([j+value, k]) for j,k in zip(high[:w-weight+1], high[weight:])]
        high = renewal
print(high[w])

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
s = 0
wts = []

for i in range(n):
    e = list(map(int, input().split()))
    s += e[1]
    wts.append(e)
    
w = min(s, w)
    
dp = [[0]*(w+1) for i in range(n)]
dp[0][wts[0][0]] = wts[0][1]

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

print(max(dp[-1]))

Submission status: Runtime Error

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

MAX_V = 10**5
dp = [[10**(18)]*(MAX_V+1) for _ in range(N+1)]
dp[0][0] = 0

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

ans = 0
for j in range():
  if dp[N][j] <= W and dp[N][j] != 10**(18):
    ans = max(ans, j)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
def main():
    N, W = map(int, input().split())
    #dp[v] vとなる最小のＷ
    dp = np.full(10**5+1, 10**9+1, dtype=np.int64)
    for _ in range(N):
        w,v = map(int, input().split())
        for val in range(10**5, 1, -1):
            if val - v < 1:
                break
            dp[val] = min(dp[val], dp[val - v] + w)
        if dp[v] > w:
            dp[v] = w
    print(max(np.where(dp <= W)[0]))
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

W0 = WV[0][0]
V0 = WV[0][1]

def initial(w):
    if w >= W0:
        return V0
    else:
        return 0
dp[0] = [initial(w) for w in range(W+1)]

def calcu(n,w):
    i = n-1
    if dp[i][w] != -1:
        return dp[i][w]

    w_i = WV[i][0]
    if w >= w_i:
        res = max(calcu(i-1, w-w_i)+WV[i][1], calcu(i-1,w))

    else:
        res = calcu(i-1,w)
    dp[i][w] = res
    return res


calcu(N, W)
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
# E Knapsack 2

import sys

sys.setrecursionlimit(10**8)

MAX_V = 10**5+1
n, w = map(int,input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)]

dp = [[float("Inf")] * (MAX_V) for _ in range(n+1)]
dp[0][0] = 0
memo = [[False] * (MAX_V) for _ in range(n+1)]
memo[0] = [True] * (MAX_V)

def dp_solve(i, j):
    if memo[i][j]:
        return dp[i][j]
    _w,_v = wv_list[i-1]
    _ret = 0
    if j-_v < 0:
        _ret = dp_solve(i-1, j)
    else:
        _ret = min(dp_solve(i-1, j), dp_solve(i-1, j-_v) + _w)
    dp[i][j] = _ret
    memo[i][j] = True
    return _ret

print(dp_solve(n, w))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
WV = []
for _ in range(N):
    WV.append(list(map(int, input().split())))
V = [v for w, v in WV]
INF = 10**10
v_max = sum(V)
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0.0
ans = 0
for i in range(N):
    for j in range(v_max+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
            #print(i, j, dp[i+1][j], dp[i][j], wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
        if i+1 == N and dp[i+1][j] <= W:
            ans = j
print(int(ans))