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 numpy as np

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

dp = np.full(N*1000+1, 10 ** 10, dtype=np.int64)
dp[0] = 0
for n in range(1, N+1):
    weight, value = inputs[n-1][0], inputs[n-1][1]
    dp[value:] = np.minimum(dp[value:], dp[:-value] + weight)

print(np.max(np.where(dp <=

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = np.zeros(W+1, dtype=np.int64)
for n in range(1, N+1):
    weight, value = inputs[n-1][0], inputs[n-1][1]
    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value)

print(dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = np.zeros(W+1, dtype=np.int64)
for n in range(1, N+1):
    weight, value = inputs[n-1][0], inputs[n-1][1]
    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value)

print(dp[-1])

Submission status: Runtime Error

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

DP = [-1] * (W+1)
DP[W] = 0

def maxv(i, v):
    if i >= 0:
        if v > DP[i]:
            DP[i] = v

for w, v in (map(int, input().split()) for _ in range(N)):
    for i in range(1, W+1):
        if DP[i] >= 0:
            maxv(i-w, DP[i]+v)
            maxv(0, DP[i-w])

print(DP[0])

Submission status: Runtime Error

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

lis = [list(map(int,input().split())) for i in range(n)]
lis.sort(key = lambda x:x[1])

dp = {0:0}

for weight ,value in lis:
    gone = dp.copy()
    for key in dp:
        gone[key+value] = min(dp[key] + weight, dp.get(key+v, float("inf")))
    dp = gone
for key in sorted(dp.keys(), reverse = True):
    if dp[key] <= w:
        print(key)
        exit()

Submission status: Runtime Error

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

N,W = map(int,input().split())
wvs = [[int(kk) for kk in input().split()] for i in range(N)]

dp = [0]*(W+1)

for w,v in  wvs:
    for i in reversed(range(W+1)):
        #print(i)
        dp[i] = max(dp[i-w]+v,dp[i])
        if i == w:
            break

print(max(dp))

Submission status: Runtime Error

Solution code:
inf = float('inf')

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

M = N*sum(v)

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

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

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

print(ans)

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]+v, dp[w:], out=dp[w:])

print(dp[-1])

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

sys.setrecursionlimit(1000000)
# MOD = 10 ** 9 + 7
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

N, W = [int(x) for x in input().split()]

dp = [float('inf')] * 1000 * 100
vs = set()
vs.add(0)
dp[0] = 0

for i in range(N):
    w, v = [int(x) for x in input().split()]

    tmpDP = dp.copy()
    for vv in list(vs):
        if dp[vv + v] > dp[vv] + w:
            # print(
            #     "(w,v)=({0},{1}): dp[{2}]:{3} dp[{4}]:{5} --> {6}".format(w, v, vv, dp[vv], vv + v, dp[vv + v],
            #                                                                dp[vv] + w))
            tmpDP[vv + v] = dp[vv] + w
            vs.add(vv + v)
    dp = tmpDP

# for i in range(len(dp)):
#     if dp[i] < float('inf'):
#         print("{}, {}".format(i, dp[i]))

ans = 0
for v in list(vs):
    # print("{}, {}".format(v, dp[v]))
    if dp[v] <= W:
        ans = max(ans, v)
print(ans)

Submission status: Runtime Error

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

NAN = float('inf')
V_MAX = 10000
dp = [NAN] * (V_MAX+1)
dp[0] = 0

for i in range(0,N):
    w = WS[i]
    v = VS[i]
    for j in reversed(range(0,V_MAX+1)):
        if dp[j] != NAN:
            dp[j+v] = min(dp[j+v], dp[j]+w)

for v in reversed(range(0,V_MAX+1)):
    w = dp[v]
    if w <= W:
        print(v)
        exit(0)

Submission status: Runtime Error

Solution code:
from numpy import*
N,W=map(int, input().split())
dp=zeros(W+1)
for i in range(N):
    w,v=map(int, input().split())
    dp[w:]=maximum(dp[w:], dp[:-w]+v)
print(int(dp[W]))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
# dp[i][w] : i個目の時の重さwの最大値
dp = [[0] * 100010 for _ in range(N+1)]
for i in range(N):
    w_i, v_i = map(int, input().split())
    for w in range(W+1):
        if w >= w_i:
            dp[i+1][w] = max(dp[i][w-w_i]+v_i, dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
a=[[0,0] for _ in range(n)]
vw=[[0,0] for _ in range(n)]
for j in range(n):
    a[j][0],a[j][1]=map(int,input().split())
    vw[j][0],vw[j][1]=a[j][1]/a[j][0],j
vw.sort(reverse=True)
#print(vw,a)
j=0
v=0
while(w>0):
   # print(w,a[vw[j][1]][0],a)
    d=min(w,a[vw[j][1]][0])
    #print(d)
    v=v+d*vw[j][0]
    w=w-d
    a[j][1]-=d
    #print(v, w, a[j][1],vw[j][0]*d)
    j+=1
  #  print(v,w,a[j][1])
print(int(v))

Submission status: Runtime Error

Solution code:
from numpy import*
N,W=map(int, input().split())
dp=zeros(W+1)
for i in range(N):
    w,v=map(int, input().split())
    dp[w:]=maximum(dp[w:], dp[:-w]+v)
    print(dp)
print(int(dp[W]))

Submission status: Runtime Error

Solution code:
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

N,W=LI()
INL = [tuple(LI()) for i in range(N)]
DP=[[10**18]*10001 for _ in range(N+1)]
DP[0][0] = 0

for i, (w, v) in enumerate(INL, 1):
    for j in range(100001):
        INL[i][j] = INL[i-1][j]
        if j + v <= 100000:
            INL[i][j+v] = INL[i-1][j]+w

res = 0
for v, w in enumerate(INL[N]):
    if w <= W:
        res = max(res, v)

print(res)

Submission status: Runtime Error

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

inf = float("inf")

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

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

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

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())
# dp = np.zeros((N+1, W+1))  #i個目の品物までで重さw以下のときの価値の最大値 
# """
# dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
#          = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
# """
# for i in range(1, N+1):
#     wi, vi = map(int, input().split())
#     for k in range(1, i+1):
#         tmp = np.maximum(dp[i-k, :W-wi+1] + vi, dp[i-k, wi:W+1])
#         dp[i, wi:W+1] = np.maximum(dp[i, wi:W+1], tmp)
    

# print(int(dp[-1,-1]))


N, W = map(int, input().split())
# dp = np.zeros((N+1, W+1))  #i個目の品物までで重さw以下のときの価値の最大値 
dp = [[0]*(W+1) for _ in range(N+1)]
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""

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

    for j in range(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[-1][-1])

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)]
for i in range(n):
    for j in range(w + 1):
        if 0 <= j - goods[i][0]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - goods[i][0]] + goods[i][1])
        dp[i][j] = max(dp[i][j], dp[i - 1][j])
print(dp[n - 1][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 range(n):
    for j in range(w + 1):
        if 0 <= j - goods[i][0]:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - goods[i][0]] + goods[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())
goods = [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 0 <= j - goods[i][0]:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - goods[i][0]] + goods[i][1])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

for i in range(n + 1):
    print(dp[i])
print(dp[n][w])

Submission status: Runtime Error

Solution code:
#import sys
#input=sys.stdin.readline
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())
V=sum(v)
dp=[[float('inf')*(V+1)] for i in range(N+1)] #初期化はfor より *の方が早い

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

for j in range(V+1):
    if dp[N][j]<=W:
        res=j
print(res)
# stdinなし

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] = 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:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[float('inf')] * (N * 1000 + 1) for _ in range(N+1)]
    dp[0][0] = 0

    for i, (cw, cv) in enumerate(zip(w, v)):
        for j in range(N * 1000 + 1):
            dp[i+1][j] = dp[i][j]
            if 0 <= (j - cv) and (dp[i][j - cv] + cw) <= W:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j - cv] +  cw)

    return max([cv for cv, cw in enumerate(dp[-1]) if isfinite(cw)])


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
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    result = solve(N, W, w, v)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    N, W = map(int, input().split())
    WV = []
    for _ in range(N):
        w, v = map(int, input().split())
        WV.append((w, v))
    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] = max(
                    dp[i][j],
                    dp[i][j - WV[i][0]] + WV[i][1]
                )
            else:
                dp[i + 1][j] = dp[i][j]
    print(dp[-1][-1])


main()

Submission status: Runtime Error

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

import math
INF = math.inf
V = 10 ** 5 + 10

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

for i, (w, v) in enumerate(WV):
	for n in range(V):
		if v <= n:
			dp[i + 1][n] = min(dp[i + 1][n], dp[i][n - v] + w)
		dp[i + 1][n] = min(dp[i + 1][n], dp[i][n])
"""
for line in dp:
	for cell in line:
		if cell == INF:
			print("  INF", end="")
		else:
			print("{:5d}".format(cell), end="")
	print()
"""
r = 0
for i in range(V):
	if dp[-1][i] <= W:
		r = i
print(r)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
wv = [list(map(int,input().split())) for i in range(N)]

wv.sort()
wv.reverse()

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

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
#define TM_T template <class T>
using namespace std;
typedef long long ll;
TM_T T inp(){T it;cin >> it;return it;}

int N, W;
vector<ll> w;
vector<ll> v;
vector<ll> dp;

int input(){
  cin >> N >> W;
  REP(i,N) {
    w.push_back( inp<ll>() );
    v.push_back( inp<ll>() );
  }
}

int main()
{
  input();
  
  REP(i,202000+2) dp.push_back( INF ); //v
  dp[0] = 0;
  
  REP(i,N){
    ll iw = w[i];
    ll iv = v[i];
    REPR(j,200000+2){
      dp[j+iv] = min( dp[j+iv], dp[j] + iw );
    }
  }
  
  ll maxv = 0;
  REP(i,202000){
    if (dp[i]<=W){
       maxv = i;
    }
  }
  cout << maxv << endl;
}

Submission status: Runtime Error

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

Vmax=sum(V)

#dp[i][v]=i番目の品物までだけを選び価値の合計をvとしたときの必要な重量の最小値

dp = []
for _ in range(N):
	dp.append([None]*(Vmax+1))

dp[0][V[0]+1] = W[0]

for i in range(1,N):
	#新しく積めるようになる荷物の価値をV[i]とする
	#このとき価値の合計をvにするのに必要な重量の最小値は
	#	dp[i-1][v-V[i]]+W[i] と
	# dp[i-1][v] のうち小さいほう
	for v in range(Vmax+1):
		if v-V[i]<0:
			dp[i][v] = dp[i-1][v]
		else:
			if dp[i-1][v]:
				if dp[i-1][v-V[i]]:
					dp[i][v] = min(dp[i-1][v],dp[i-1][v-V[i]]+W[i])
				else:
					dp[i][v] = dp[i-1][v]
			else:
				if dp[i-1][v-V[i]]:
					dp[i][v] = dp[i-1][v-V[i]]+W[i]

ans = 0
for v in range(Vmax+1):
	try:
		ans = v if dp[-1][v]<=Wmax else ans
	except TypeError:
		pass

print(ans)

Submission status: Runtime Error

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

Vmax=(10**3)*N

#dp[i][j]=i番目の品物までだけを選び価値の合計をvとしたときの必要な重量の最小値

dp = []
for _ in range(N):
	dp.append([0]*(Vmax+1))

dp[0][V[0]] = W[0]

for i in range(1,N):
	#新しく積めるようになる荷物の価値をV[i]とする
	#このとき価値の合計をvにするのに必要な重量の最小値は
	#	dp[i-1][v-V[i]]+W[i] と
	# dp[i-1][v] のうち小さいほう
	for v in range(Vmax+1):
		if v-V[i]<0:
			dp[i][v] = dp[i-1][v]
		else:
			dp[i][v] = min(dp[i-1][v], dp[i-1][v-V[i]]+W[i])

ans = 0
for v in range(Vmax+1):
	ans = v if dp[-1][v] <= W else ans

print(ans)

Submission status: Runtime Error

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

big = 5*10**8

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp_small = [0]*(min(Wmax+1,big+1))
for i in range(len(dp_small)):
	if i >= W[0]:
		dp_small[i] = V[0]

#dp_large[0] = dp_small[-1]
dp_large = []
dp_large.append(dp_small[-1])
for i in range(max(0,Wmax-big)):
	if i+big >= W[0]:
		dp_large[i] = V[0]


for i in range(1,N):
	#今回の重量制限をwとする
	#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
	#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
	#よってこの2つのうち大きいほうをdp[i][w]に採用する
	dp_small_new = []
	dp_large_new = []
	for j in range(Wmax+1):
		if j<=big:
			if j<W[i]:
				dp_small_new.append(dp_small[j])
			else:
				dp_small_new.append(max(dp_small[j], dp_small[j-W[i]]+V[i]))
			if j==big:
				dp_large_new.append(dp_small_new[-1])
		else:
			if j<W[i]:
				dp_large_new.append(dp_large[j])
			elif j-W[i]<=big:
				dp_large_new.append(max(dp_large[j], dp_small[j-W[i]]+V[i]))
			else:
				dp_large_new.append(max(dp_large[j], dp_large[j-W[i]-big]+V[i]))
	dp_small = dp_small_new
	dp_large = dp_large_new
print(dp_small[Wmax]) if Wmax<=big else print(dp_large[Wmax-big])

Submission status: Runtime Error

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

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp_last = [0]*(Wmax+1)
for i in range(Wmax+1):
	if i >= W[0]:
		dp_last[i] = V[0]

for i in range(1,N):
	#今回の重量制限をwとする
	#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
	#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
	#よってこの2つのうち大きいほうをdp[i][w]に採用する
	dp = []
	for j in range(Wmax+1):
		if j<W[i]:
			dp.append(dp_last[j])
		else:
			dp.append(max(dp_last[j], dp_last[j-W[i]]+V[i]))
	dp_last = dp
print(dp[Wmax])

Submission status: Runtime Error

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

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp_last = []
dp_last.append([0]*min(W[0],Wmax+1)+ [V[0]]*max(0, Wmax+1-W[0]))


for i in range(1,N):
	#今回の重量制限をwとする
	#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
	#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
	#よってこの2つのうち大きいほうをdp[i][w]に採用する
	dp = []
	for j in range(Wmax+1):
		if j<W[i]:
			dp.append(dp_last[j])
		else:
			dp.append(max(dp_last[j], dp_last[j-W[i]]+V[i]))
	dp_last = dp
print(dp[Wmax])

Submission status: Runtime Error

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

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp = []
dp.append([0]*min(W[0],Wmax+1)+ [V[0]]*max(0, Wmax+1-W[0]))


for i in range(1,N):
	#今回の重量制限をwとする
	#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
	#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
	#よってこの2つのうち大きいほうをdp[i][w]に採用する
	dpi = []
	for j in range(Wmax+1):
		if j<W[i]:
			dpi.append(dp[i-1][j])
		else:
			dpi.append(max(dp[i-1][j], dp[i-1][j-W[i]]+V[i]))
	dp.append(dpi)
print(dp[N-1][Wmax])

Submission status: Runtime Error

Solution code:
def e():
    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] >= 0:
                dp[i + 1][j] = max(dp[i + 1][j],
                                   dp[i][j - wv[i][0]] + wv[i][1])
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
    return dp[-1][-1]


if __name__ == '__main__':
    ans = e()
    print(ans)

Submission status: Runtime Error

Solution code:
def knapsack():
    n, max_w = map(int, input().split())
    dp = defaultdict(int)
    dp[0] = 0
    for _ in range(n):
        w, v = map(int, input().split())
        for item in list(dp.keys()):
            dp[item+w] = max(dp[item] + v, dp[item+w])
    max_v = 0
    for w, v in dp.items():
        if w <= max_w:
            max_v = max(v, max_v)
    print(max_v)
    
    
knapsack()

Submission status: Runtime Error

Solution code:
def task(N, W, weight, value, result_dict):
    if (N == 0) or (W == 0):
        return 0
    if (N, W) in result_dict:
        return result_dict[(N, W)]
    if weight[N - 1] <= W:
        a = task(N-1, W, weight, value, result_dict)
        b = task(N, W - weight[N - 1], weight, value, result_dict) + value[N - 1]
        result_dict[(N, W)] = max(a, b)
    else:
        result_dict[(N, W)] = task(N-1, W)
    
    return result_dict[(N, W)]
  
N, W = [int(x) for x in input().split()]
weight,value = [], []
for i in range(N):
    w, v = [int(x) for x in input().split()]
    weight.append(w)
    value.append(v)

result_dict = {}
task(N, W, weight, value, result_dict)

Submission status: Runtime Error

Solution code:
import sys
n,w=list(map(int, sys.stdin.readline().split()))
arr=[list(map(int, sys.stdin.readline().split())) for i in range(n)]

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

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


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

Submission status: Runtime Error

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

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


for i in range(N):
    for sum_w in range(0,W+1):
        if sum_w - cost[i][0] >= 0:
            dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w - cost[i][0]] + cost[i][1])
        dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

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

Submission status: Runtime Error

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

n, W = [int(i) for i in input().split()]
dp = [W + 1] * (1010 * (n + 1))

dp[0] = 0
v_max = 0
for i in range(n):
    w, v = map(int, input().split())
    v_max += v
    for j in range(v_max, v - 1, -1):
        dp[j] = min(dp[j - v] + w, dp[j])

ans = 0
for i in range(v_max, -1, -1):
    if dp[i] <= W:
        ans = max(ans, i)
print(ans)

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
dp = [0] * (W + 1)

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

Submission status: Runtime Error

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

for i in range(n):
    w, v = map(int, input().split())
    for j in range(W + 1):
        if j >= w:
            dp[i + 1][j] = max(dp[i][j - w] + v, dp[i][j])
        else:
            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())
dp = np.zeros((n + 1, W + 1))

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

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
    num, weigh = map(int, input().split())
    dp = np.zeros((num + 1, weigh + 1), dtype=int)

    for i in range(1, num + 1):
        now_weigh, now_value = map(int, input().split())
        dp[i, :now_weigh] = dp[i - 1, :now_weigh]
        dp[i, now_weigh:] = np.maximum(dp[i - 1, :weigh - now_weigh + 1] + now_value, dp[i - 1, now_weigh:])

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
val = [0]*(W+1)
for i in range(N):
  w, v = map(int, input().split())
  for j in reversed(range(w,W+1)):
    val[j] = max(val[j], val[j-w] + v) 
print(val[W])

Submission status: Runtime Error

Solution code:
import sys
from itertools import accumulate as acc

def main():
    N, W = map(int, input().split())
    V = [[] for _ in '1234']

    w, v = map(int, input().split())
    w0 = w
    V[0].append(v)
    for e in sys.stdin:
        w, v = map(int, e.split())
        V[w - w0].append(v)

    for i in range(4):
        V[i] = [0] + list(acc(sorted(V[i], reverse=True)))

    ans = 0
    a, b, c, d = map(len, V)
    for i in range(a):
        wi = w0 * i
        if wi > W:
            break
        vi = V[0][i]
        for j in range(b):
            wj = wi + (w0 + 1) * j
            if wj > W:
                break
            vj = vi + V[1][j]
            for k in range(c):
                wk = wj + (w0 + 2) * k
                if wk > W:
                    break
                vk = vj + V[2][k]

                l = min((W - wk) // (w0 + 3), d - 1)
                v = vk + V[3][l]
                ans = max(ans, v)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N, W = [int(x) for x in stdin.readline().rstrip().split()]
wv = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

# 最大公約数を求めてWを何とか小さくする
gcd_num = W
for i in range(N):
    gcd_num = fractions.gcd(gcd_num, wv[i][0])

W = W // gcd_num
for i in range(N):
    wv[i][0] = wv[i][0] // gcd_num

# 重さiでの価値の最大
# 品物の重複選択を許さない
dp = [[0] * (W+10) for _ in range(N+10)]

for i in range(N):
    weight, value = wv[i]
    dp[i+1] = dp[i][:]
    for j in range(weight, W+1):
        dp[i+1][j] = max(dp[i][j], dp[i][j-weight]+value)

print(dp[N][W])

Submission status: Runtime Error

Solution code:
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(int(dp[-1]))

Submission status: Runtime Error

Solution code:
import numpy as np
N, W = map(int,input().split())
#普通に書くとTLEだったのでNumpy化
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(int(dp[-1]))

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = np.ones([2, N * 10 ** 3 + 1], dtype=int) * float("inf")
dp[0][0], dp[1][0] = 0, 0
for i in range(N):
    index = i % 2
    w, v = map(int, input().split())
    for j in range(1, len(dp[0])):
        if j <= v:
            dp[index][j] = min(w, dp[index-1][j])
        else:
            dp[index][j] = min(w + dp[index-1][j-v], dp[index-1][j])

dp = np.minimum(dp[0], dp[1])
ans = 0
for i, w in enumerate(dp):
    if w <= W:
        ans = max(ans, i)
    else:
        break

print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
input = stdin.readline
N, W = list(map(int, input().split()))
wvList = [list(map(int, input().split())) for _ in range(N)]
v_sum = sum([wv[1] for wv in wvList])

V_list = np.zeros(v_sum)

import numpy as np

for wv in wvList:
    w,v = wv
    V_list=np.hstack((V_list[:v],np.maximum(V_list[:-v]+w,V_list[v:])))
for idx,v in enumerate(V_list):
    if v>=W:
        print(idx)
        break

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
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:
N, W = map(int, input().split())
WV = (map(int, input().split()) for _ in range(N))

DP = [0] * (W+1)

for w, v in WV:
  for j in range(W, w-1, -1):
    dp = DP[j-w] + v 
    if DP[j] < dp:
      DP[j] = dp
print(max(DP))

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
w, v = [], []

for _ in range(n):
    i, j = map(int, input().split())
    w.append(i), v.append(j)

sum_value = sum(v)
dp = [1e9] + [1e9] * sum_value
dp[0] = 0

for i in range(n):
    for j in range(sum_value - v[i], -1, -1):
        dp[j + v[i]] = min(dp[j + v[i]], dp[j] + w[i])

print(dp.rindex(max(list(filter(lambda x : x <= W, dp)))))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
 
n,w=map(int,input().split())
dp=[0]*(w+1)
 
def ans(n,w):
  for _ in range(n):
    c,p=map(int,input().split())
    for j in range(w,c-1,-1):
      tmp=dp[j-c]+p
      if dp[j]<tmp:
        dp[j]=tmp
  return max(dp)
print(ans(n,w))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nms = lambda: map(str, sys.stdin.readline().split())
nl = lambda: list(nm())

n, w = nm()
lis = [nl() for _ in range(n)]
lis.insert(0, [0, 0])
dp = np.zeros(w + 1, dtype=np.int64)

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

print(dp[-1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3

import numpy as np

def main():
    N, W = map(int, input().split())

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

    for i in range(N):
        weight, value = map(int, input().split())

        dp[i+1][:weight] = dp[i][:weight]
        dp[i+1][weight:] = np.maximum(dp[i][weight:], dp[i][:-weight] + value)

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

import sys
sys.setrecursionlimit(1000000)

n, W = map(int, input().split())
dp = np.zeros(W+1,'i8')
for i in range(n):
  w, v = map(int, input().split())
  #print(dp[w:],dp[:-w],dp)
  dp[w:] = np.maximum(dp[w:], dp[:-w]+v)
  #print(dp[w:],dp[:-w],dp)
print(dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
n, W = map(int, input().split())
dp = np.zeros(W+1,'i8')
for i in range(n):
  w, v = map(int, input().split())
  #print(dp[w:],dp[:-w],dp)
  dp[w:] = np.maximum(dp[w:], dp[:-w]+v)
  #print(dp[w:],dp[:-w],dp)
print(dp[-1])