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: Wrong Answer

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

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

for i in range(N):
  w, v = map(int, input().split())
  for j in range(10**3 + 1):
    dp[i+1][j] = min(dp[i][j], dp[i][max(0, j-v)] + w)

for i, x in enumerate(dp[-1]):
  if x <= W:
    ans = i

print(ans)

Submission status: Wrong Answer

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

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

for i in range(N):
  w, v = map(int, input().split())
  for j in range(10**3 + 1):
    if j <= v:
      dp[i+1][j] = min(dp[i][j], w)
    else:
      dp[i+1][j] = min(dp[i][j], dp[i][j-v] + w)

for i, x in enumerate(dp[-1]):
  if x <= W:
    ans = i

print(ans)

Submission status: Wrong Answer

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

INF = 10**9 + 1
dp = [[INF]*(10**3 + 1) for _ in range(N+1)]

for i in range(N):
  w, v = map(int, input().split())
  for j in range(10**3 + 1):
    if j <= v:
      dp[i+1][j] = min(dp[i][j], w)
    else:
      dp[i+1][j] = min(dp[i][j], dp[i][j-v] + w)

for i, x in enumerate(dp[-1]):
  if x <= W:
    ans = i

print(ans)

Submission status: Wrong Answer

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)
V=sum(v)
INF=10**18
dp=[[INF for _ in range(V+1)] for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
  for j in range(V+1):
    if j<v[i]:dp[i+1][j]=dp[i][j]
    else:dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
for i in range(V):
  if dp[n][i]<=W:ans=i
print(ans)

Submission status: Wrong Answer

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

def main():
    n, w = map(int,input().split())
    wei = []
    val = []
    for i in range(n):
        a, b = map(int,input().split())
        wei.append(a)
        val.append(b)

    max_v = 10**3
    dp = [[float('inf') for i in range(max_v+1)] for j in range(n+1)]

    dp[0][0] = 0

    for i in range(n):
        for sum_v in range(max_v):

            
            if sum_v - val[i] >= 0:
                dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - val[i]] + wei[i])

            
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

    res = 0
    for sum_v in range(max_v):
        if dp[n][sum_v] <= w:
            res = sum_v

    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#dp[i][j]:iまでで価値jになるようにするときの品物の重さ
#答えはdp[N]をjが大きいものから見ていってWより小さいもの

INF = 10*12

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

dp = [[INF]*(100*1000+1) for i in range(N)]
for i in range(N):
    dp[i][0]=0
dp[0][v[0]]=w[0]

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

for j in range(100*1000,-1,-1):
    if dp[N-1][j] <= W:
        print(j)
        exit()

Submission status: Wrong Answer

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

INF = 10**12

# 各valueの値に対する最小のweightを記録する
dp = [[INF] * (10**4) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    w, v = wv[i]
    for j in range(10**4):
        if j < v:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-v]+w)
for i in range(10**4-1, 0, -1):
    if dp[N][i] <= W:
        print(i)
        break

Submission status: Wrong Answer

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

INF = 10**12

# 各valueの値に対する最小のweightを記録する
dp = [[INF] * (10**3+5) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    w, v = wv[i]
    for j in range(10**3+5):
        if j < v:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-v]+w)
for i in range(10**3+4, 0, -1):
    if dp[N][i] <= W:
        print(i)
        break

Submission status: Wrong Answer

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

INF = 10**12

# 各valueの値に対する最小のweightを記録する
dp = [[INF] * (10**3+5) for _ in range(N+1)]
dp[0][0] = 0

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

for i in range(10**3+4, 0, -1):
    if dp[N][i] <= W:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
n,lw=map(int,input().split())
item=[]
for i in range(n):
    inp0,inp1=map(int,input().split())
    item.append((inp0,inp1))

dp=[10**13 for i in range(1001*n)]
dp[0]=0

for i in range(n):
    w=item[i][0]
    v=item[i][1]
    for q in range(1001*n-1,-1,-1):
        if q<=v:
            dp[q]=min(dp[q], w)
        else:
            dp[q]=min(dp[q], dp[q-v]+w)

for i in range(1001*n):
    if dp[i]>lw:
        print(i-1)
        break

Submission status: Wrong Answer

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

sumValues = sum(values)
dp = [float('inf')] * (sumValues + 1) # Minimum weight at value v.
dp[0] = 0
for item in range(N):
  for value in range(sumValues-values[item], -1, -1):
    dp[value+values[item]] = min(dp[value+values[item]], dp[value]+weights[item])

res = 0
for i in range(sumValues):
  if dp[i] <= W:
    res = max(res, i)
print(res)

Submission status: Wrong Answer

Solution code:
N, W = (int(x) for x in input().split())
values = []
weights = []
sumValues = 0
sumWeights = 0
for _ in range(N):
  w, v = (int(x) for x in input().split())
  sumValues += v
  sumWeights += w
  values.append(v)
  weights.append(w)

zipped = zip(values, weights)

placeholder = 1000000
dp = [placeholder] * (sumValues+1) # Min weight at value v.
dp[sumValues] = sumWeights

for itemValue, itemWeight in list(zipped):
  for cur in range(itemValue, sumValues+1):
    if dp[cur] != placeholder:
      dp[cur-itemValue] = min(dp[cur-itemValue], dp[cur]-itemWeight)

res = 0
for i in range(len(dp)):
  if dp[i] <= W:
    res = max(i, res)

print(res)

Submission status: Wrong Answer

Solution code:
N, W = (int(x) for x in input().split())
values = []
weights = []
sumValues = 0
sumWeights = 0
for _ in range(N):
  w, v = (int(x) for x in input().split())
  sumValues += v
  sumWeights += w
  values.append(v)
  weights.append(w)

zipped = zip(values, weights)

placeholder = 100000
dp = [placeholder] * (sumValues+1) # Min weight at value v.
dp[sumValues] = sumWeights

for itemValue, itemWeight in list(zipped):
  for cur in range(itemValue, sumValues+1):
      dp[cur-itemValue] = min(dp[cur-itemValue], dp[cur]-itemWeight)

res = 0
for i in range(len(dp)):
  if dp[i] <= W:
    res = max(i, res)

print(res)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 9 + 5
V = 1001
dp = [[INF] * V for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V):
        w = wv[i][0]
        v = wv[i][1]
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        if j - v >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v] + w)

for i in range(V):
    if dp[N][i] <= W:
        MV = i    
print(MV)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 9 + 5
V = 1001
dp = [[INF] * V for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V):
        w = wv[i][0]
        v = wv[i][1]
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        if j - v >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v] + w)

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

Submission status: Wrong Answer

Solution code:
######################################################
############Created by Devesh Kumar###################
#############devesh1102@gmail.com####################
##########For CodeForces(Devesh1102)#################
#####################2020#############################
######################################################
import sys
input = sys.stdin.readline

# import sys
import heapq 
import copy
import math
import decimal
# import sys.stdout.flush as flush
# from decimal import *
#heapq.heapify(li) 
#
#heapq.heappush(li,4) 
#
#heapq.heappop(li)
#
# &	Bitwise AND Operator	10 & 7 = 2
# |	Bitwise OR Operator	10 | 7 = 15
# ^	Bitwise XOR Operator	10 ^ 7 = 13
 
# <<	Bitwise Left Shift operator	10<<2 = 40
# >>	Bitwise Right Shift Operator
# '''############ ---- Input Functions ---- #######Start#####'''
 

def inp():
	return(int(input()))
def inlt(): 
	return(list(map(int,input().split())))
def insr():
	s = input()
	return(list(s[:len(s) - 1]))
def insr2():
	s = input()
	return((s[:len(s) - 1]))
def invr():
	return(map(int,input().split()))
 ############ ---- Input Functions ---- #######End
 # #####   

def pr_list(a):
	print(*a, sep=" ")
def main():
	# tests =  inp()
	tests = 1
	mod = 998244353
	limit = 10**18
	ans = 0
	for test in range(tests):
		[n,w] = inlt()
		val = []
		maxi = 0
		for i in range(n):
			a = inlt()
			maxi = maxi + a[0]
			val.append(a)
		if w>=maxi:
			print(maxi)
			continue
		dp = [[-1 for i in range(w+3)]for j in range(2)]
		dp[0][0] = 0
		ans = 0
		for i in range(n):
			
			for j in range(w+3):
				dp[(i+1)%2][j] = max(dp[(i+1)%2][j],dp[(i)%2][j])
				if dp[i%2][j] != -1 and j + val[i][0]<=w:
					dp[(i+1)%2][j+val[i][0]] = max(	dp[(i)%2][j+val[i][0]] , 	dp[(i)%2][j] + val[i][1])
					ans = max(ans,dp[(i+1)%2][j+val[i][0]] )
		print(ans)

if __name__== "__main__":
	main()

Submission status: Wrong Answer

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]
ans = 0
for j in range(m+1):
        if dp[N][j] <= W:
            ans = max(ans,j)
print(ans)

Submission status: Wrong Answer

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]
print(dp)
ans = 0
for j in range(m+1):
        if dp[N][j] <= W:
            ans = max(ans,j)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, w = map(int, input().split())
wv = np.array([list(map(int, input().split())) for _ in range(n)])

V = wv[:, 1].sum()
INF = 1 << 60
dp = np.full([n + 1, V + 1], INF, np.int64)
dp[0][0] = 0

for i in range(1, n + 1):
    for j in range(1, V + 1):
        if (j - wv[i - 1][1] >= 0):
            dp[i][j] = min(dp[i][j], dp[i - 1][j - wv[i - 1][1]] + wv[i - 1][0])
        else:
            dp[i][j] = min(dp[i][j], dp[i - 1][j])

ans = 0
for arr in np.where(dp <= w):
    ans = max(ans, arr.max())

print(ans)

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
l=[[0,0]]
for _ in range(n):
    l.append(list(map(int,input().split())))
dp=[[10**10]*(n*(10**3)+1) for _ in range(n+1)]
for k in range(n+1):
    dp[k][0]=0
for i in range(1,n+1):
    for j in range(0,n*(10**3)+1):

        if j>=l[i][1]:
            assert n>=i-1>=0
            assert n*(10**3)>=j>=0
            assert n*(10**3)>=j-l[i][1]>=0
            assert len(l[i])==2
            dp[i][j]=min(dp[i-1][j-l[i][1]]+l[i][0],dp[i-1][j])
        else:
            dp[i][j]=min(dp[i-1][j],l[i][1])
print(max([i for i,x in enumerate(dp[n]) if x<=w]))

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

# ここから書き始める
n, w = map(int, input().split())
dp = [[INF for j in range(10 ** 5 + 1)] for i in range(n)]
for i in range(n):
    weight, value = map(int, input().split())
    if i == 0:
        dp[i][value] = weight
        continue
    for j in range(10 ** 5 + 1):
        dp[i][j] = dp[i - 1][j]
        if 0 <= j - value:
            dp[i][j] = min(dp[i][j], dp[i - 1][j - value] + weight)
ans = 0
# print(dp)
for i in reversed(range(10 ** 5 + 1)): 
    if dp[-1][i] <= w:
        ans = i
        break
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n, W = list(map(int, input().split()))
    V = 1000
    INF = float('inf')
    dp = [[INF] * (V + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    for i in range(1, n + 1):
        w, v = list(map(int, input().split()))
        for j in range(V + 1):
            if v > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = min(dp[i - 1][j - v] + w, dp[i - 1][j])
    ans = V
    while dp[n][ans] > W:
        ans -= 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, W = list(map(int, input().split()))
    V = 1000
    INF = float('inf')
    dp = [[INF] * (V + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    ans = 0
    for i in range(1, n + 1):
        w, v = list(map(int, input().split()))
        for j in range(V + 1):
            if v > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = min(dp[i - 1][j - v] + w, dp[i - 1][j])
            if dp[i][j] <= W:
                ans = max(ans, j)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, W = list(map(int, input().split()))
    V = 1000
    INF = float('inf')
    dp = [[INF] * (V + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    ans = 0
    for i in range(1, n + 1):
        w, v = list(map(int, input().split()))
        for j in range(V + 1):
            if v >= j:
                dp[i][j] = min(dp[i - 1][j], w)
            else:
                dp[i][j] = min(dp[i - 1][j - v] + w, dp[i - 1][j])
            if dp[i][j] <= W:
                ans = max(ans, j)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

w=[0]*N
v=[0]*N

dp=[[10**20]*(10**3+1) for _ in range(N+1)]
dp[0][0]=0

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

for i in range(N):
    for vv in range(10**3+1):
        if vv-v[i]>=0:
            dp[i+1][vv]=min(dp[i][vv],dp[i][vv-v[i]]+w[i])
        else:
            dp[i+1][vv]=dp[i][vv]

for vv in range(10**3,-1,-1):
    if dp[N][vv]<=W:
        print(vv)
        break

Submission status: Wrong Answer

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

w=[0]*N
v=[0]*N

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

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

for i in range(N):
    for vv in range(10**3+1):
        if vv-v[i]>=0:
            dp[i+1][vv]=min(dp[i][vv],dp[i][vv-v[i]]+w[i])
        else:
            dp[i+1][vv]=dp[i][vv]

for vv in range(10**3,-1,-1):
    if dp[N][vv]<=W:
        print(vv)
        break

Submission status: Wrong Answer

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(i,w):
    print(i,w)
    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-1, W)
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
INF = 10**10
v_max = 10**5
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[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]
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
INF = 10 ** 11 + 1

n, w = [int(i) for i in input().split()]

wv = [[int(i) for i in input().split()] for _ in range(n)]

dp = [[INF for _ in range(1001)] for _ in range(n)]

dp[0][0] = 0
dp[0][wv[0][1]] =wv[0][0]

for i in range(1,n):
    for j in range(1001):
        if(j-wv[i][1] >= 0):
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-wv[i][1]] + wv[i][0])
        else:
            dp[i][j] = dp[i-1][j]

ans = 0
for i in range(1,1001):
    if(dp[n-1][i] <= w):
        ans = i

print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 9 + 7

n, w = [int(i) for i in input().split()]

wv = [[int(i) for i in input().split()] for _ in range(n)]

dp = [[INF for _ in range(1001)] for _ in range(n)]

dp[0][0] = 0
dp[0][wv[0][1]] =wv[0][0]

for i in range(1,n):
    for j in range(1001):
        if(j-wv[i][1] >= 0):
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-wv[i][1]] + wv[i][0])
        else:
            dp[i][j] = dp[i-1][j]

ans = 0
for i in range(1,1001):
    if(dp[n-1][i] <= w):
        ans = i

print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 9 + 7

n, w = [int(i) for i in input().split()]

wv = [[int(i) for i in input().split()] for _ in range(n)]

dp = [[INF for _ in range(1001)] for _ in range(n)]

dp[0][0] = 0

for i in range(1,n):
    for j in range(1001):
        if(j-wv[i][1] >= 0):
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-wv[i][1]] + wv[i][0])
        else:
            dp[i][j] = dp[i-1][j]

ans = 0
for i in range(1,1001):
    if(dp[n-1][i] <= w):
        ans = i

print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 9 + 7

n, w = [int(i) for i in input().split()]

wv = [[int(i) for i in input().split()] for _ in range(n)]

dp = [[INF for _ in range(1001)] for _ in range(n)]

for i in range(n):
    dp[i][0] = 0
    if(i == 0):
        dp[i][wv[i][1]] = wv[i][0]
    else:
        for j in range(1001):
            if(j-wv[i][1] >= 0):
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-wv[i][1]] + wv[i][0])
            else:
                dp[i][j] = dp[i-1][j]

ans = 0
for i in range(1,1001):
    if(dp[n-1][i] <= w):
        ans = i

print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 9 + 7

n, w = [int(i) for i in input().split()]

wv = [[int(i) for i in input().split()] for _ in range(n)]

dp = [[INF for _ in range(1001)] for _ in range(n)]

for i in range(n):
    dp[i][0] = 0
    if(i == 0):
        dp[i][wv[i][1]] = wv[i][0]
    else:
        for j in range(1001):
            if(j-wv[i][1] >= 0):
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-wv[i][1]] + wv[i][0])
            else:
                dp[i][j] = dp[i-1][j]

for i in reversed(range(1001)):
    if(dp[n-1][i] <= w):
        print(i)
        break

Submission status: Wrong Answer

Solution code:
# D問題とほぼ同じだが計算量が問題になる．
# 前回と違い重さの制約が，W<10^9なので，重さのノードを作ってしまうと，計算量がどう仕様もなくなる
# なので，価値に対してノードを作ってあげて，最小の重さを計算するようにする

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

W = []
V = []

for i in range(N):
    w,v = map(int,input().split())
    W.append(w)
    V.append(v)
# dp[v][i] := 商品iまで選択して，価値がv以下となった場合について，最小の重さ
import math
import numpy as np
dp = np.ones((10**3*N)) * np.inf
dp[0] = 0
for v,w in zip(V,W):
    np.minimum(dp[:-v]+w, dp[v:],out=dp[v:])
print(np.where(dp<=W_max)[0][-1])

Submission status: Wrong Answer

Solution code:
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[value] - minimum weight that achieves value
    OPT[value] = OPT[value-v[i]]
    """
    return -1
    N, W = read_ints()
    max_value = 1000*N+1
    dp = [math.inf]*max_value
    dp[0] = 0
    for i in range(N):
        w, v = read_ints()
        for j in range(max_value-1, -1, -1):
            if j >= v:
                dp[j] = min(dp[j], dp[j-v]+w)
    ans = 0
    for j in range(max_value):
        if dp[j] <= W:
            ans = j
    return ans


if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
n,w=[int(k) for k in input().split()]
li=[]
 
 
ans=0
for i in range(n):
    li.append([int(k) for k in input().split()])
dp=[[0 for i in range(100001)] for j in range(n+1)]
for i in range(1,10001):
    dp[0][i]=10**10
dp[0][0]=0    
for a in range(1,n+1):
    for b in range(0,100001):
        if(li[a-1][1]<=b):
            x=li[a-1][0]+dp[a-1][b-li[a-1][1]]
            y=dp[a-1][b]
            dp[a][b]=min(x,y)
        else:
            dp[a][b]=dp[a-1][b]
        if dp[a][b]<=w:
          ans=max(ans,b)
 
 
print(ans)

Submission status: Wrong Answer

Solution code:
n,w=[int(k) for k in input().split()]
li=[]
 
 
ans=0
for i in range(n):
    li.append([int(k) for k in input().split()])
dp=[[0 for i in range(10001)] for j in range(n+1)]
for i in range(1,10001):
    dp[0][i]=10**10
dp[0][0]=0    
for a in range(1,n+1):
    for b in range(0,10001):
        if(li[a-1][1]<=b):
            x=li[a-1][0]+dp[a-1][b-li[a-1][1]]
            y=dp[a-1][b]
            dp[a][b]=min(x,y)
        else:
            dp[a][b]=dp[a-1][b]
        if dp[a][b]<=w:
          ans=max(ans,b)
 
 
print(ans)

Submission status: Wrong Answer

Solution code:
n,w=[int(k) for k in input().split()]
li=[]
 
 
ans=0
for i in range(n):
    li.append([int(k) for k in input().split()])
dp=[[0 for i in range(10001)] for j in range(n+1)]
for i in range(1,10001):
    dp[0][i]=10**10
for a in range(1,n+1):
    for b in range(0,10001):
        if(li[a-1][1]<=b):
            x=li[a-1][0]+dp[a-1][b-li[a-1][1]]
            y=dp[a-1][b]
            dp[a][b]=min(x,y)
        else:
            dp[a][b]=dp[a-1][b]
        if dp[a][b]<=w:
          ans=max(ans,b)
 
 
print(ans)

Submission status: Wrong Answer

Solution code:
n,w=[int(k) for k in input().split()]
li=[]


ans=0
for i in range(n):
    li.append([int(k) for k in input().split()])
dp=[[0 for i in range(10001)] for j in range(n+1)]
for i in range(1,10001):
    dp[0][i]=10**10
for a in range(1,n+1):
    for b in range(1,10001):
        if(li[a-1][1]<=b):
            x=li[a-1][0]+dp[a-1][b-li[a-1][1]]
            y=dp[a-1][b]
            dp[a][b]=min(x,y)
        else:
            dp[a][b]=dp[a-1][b]
        if dp[a][b]<=w:
          ans=max(ans,b)


print(ans)

Submission status: Wrong Answer

Solution code:
n,w=[int(k) for k in input().split()]
li=[]
for i in range(n):
    li.append([int(k) for k in input().split()])
dp=[[0 for i in range(10001)] for j in range(n+1)]
for i in range(1,10001):
    dp[0][i]=10**10
for a in range(1,n+1):
    for b in range(1,10001):
        if(li[a-1][1]<=b):
            x=li[a-1][0]+dp[a-1][b-li[a-1][1]]
            y=dp[a-1][b]
            dp[a][b]=min(x,y)
        else:
            dp[a][b]=dp[a-1][b]
ans=0
#print(dp)
for c in range(1000,0,-1):
    if dp[n][c]<=w:
        ans=c
        break
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
import numpy as np
dp = np.full(10**5,10**18,dtype=np.int64)
dp[0]=0
for _ in range(N):
    w,v = map(int,input().split())
    dp[v:] = np.minimum(dp[:-v] + w, dp[v:])
print(np.max(np.where(dp <= W)))

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
dp = np.full(10**5,10**18,dtype=np.int64)
dp[0]=0
for w,v in wv:
    dp[v:] = np.minimum(dp[:-v] + w, dp[v:])
print(np.where(dp<=W)[0].max())

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
dp = np.full(10**5,10**18,dtype=np.int64)
dp[0]=0
for w,v in wv:
    np.minimum(dp[v:],dp[:-v].copy()+w,out=dp[v:])
print(np.where(dp<=W)[0].max())

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
dp = np.full(10**5,10**18,dtype=np.int64)
dp[0]=0
for w,v in wv:
    np.minimum(dp[v:],dp[:-v]+w,out=dp[v:])
print(np.where(dp<=W)[0].max())

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
dp = np.full(10**5,10**18,dtype=np.int64)
dp[0]=0
for w,v in wv:
    np.minimum(dp[v:],dp[:-v]+w,out=dp[v:])
print(np.where(dp<=W)[0][-1])

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
dp = np.full(10**5,10**15,dtype=np.int64)
dp[0]=0
for w,v in wv:
    np.minimum(dp[v:],dp[:-v]+w,out=dp[v:])
print(np.where(dp<=W)[0][-1])

Submission status: Wrong Answer

Solution code:
import numpy
N, W = map(int, input().split())
memo = numpy.array([[10**9+1 for i in range(10**5)] for j in range(N)])
memo[-1][0] = 0
for n in range(N):
    w, v = map(int, input().split())
    memo[n][:v] = memo[n-1][:v]
    memo[n][v:] = numpy.fmin(memo[n-1][v:], memo[n-1][:-v]+w)
a = numpy.where(memo[-1] <= W)
print(numpy.max(a[0]))

Submission status: Wrong Answer

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

for i in range(N):
    w, v = map(int, input().split())
    wv.append([w, v])
MAX_V = 10**5+100
INF = 10**9
dp = [[INF]*MAX_V for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(MAX_V):
        if j - wv[i][1] >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
        else:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
ans = 0
for i in range(MAX_V):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = [float("INF")]*(10**3 + 1)
dp = np.array(dp)
dp[0] = 0

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

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