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:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)

V_MAX = int(1e03)+1


def main():
    # sys.stdin = open("sample.txt")
    N, W = Scanner.map_int()
    V = [Scanner.map_int() for i in range(N)]
    dp = [[INF for _ in range(V_MAX)] for _ in range(N+1)]
    dp[0][0] = 0

    for i in range(N):
        for j in range(V_MAX):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][j] = min(dp[i+1][j], dp[i][j - V[i][1]] + V[i][0])
    for i in reversed(range(V_MAX)):
        if dp[N][i] <= W:
            print(i)
            return
    print(0)
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

for i in range(N):
    for w in reversed(range(0, W+1)):
        if dp[w] != 0:
            if w + item[i][0] <= W:
                dp[w + item[i][0]] = max(dp[w +item[i][0]], dp[w] + item[i][1])
        else:
            if w + item[i][0] <= W:
                dp[w + item[i][0]] = dp[w] + item[i][1]

print(dp[W])

Submission status: Wrong Answer

Solution code:
def solve():
    N, W = map(int, input().split())
    MAX_V = 100000
    MAX_N = 100
    w = []
    v = []
    for i in range(N):
        tmpw, tmpv = map(int, input().split())
        w.append(tmpw)
        v.append(tmpv)

    dp = [[float('inf') for i in range(MAX_V+1)] for j in range(MAX_N+1)]

    dp[0][0] = 0

    for i in range(N):
        for sum_v in range(MAX_V):
            if sum_v - v[i] >= 0:
                dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i])
            
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
        
    res = 0
    for sum_v in range(MAX_V+1):
        if dp[N][sum_v] <= W:
            res = sum_v
    print(res)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
def main():
    INF = 9
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for _ in range(N)]
    sumv = sum([v for w,v in wv])
    dp = [[INF]*(sumv+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(sumv+1):
            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] = dp[i][j]
    ans = 0
    for i in range(sumv+1):
        if dp[N][i] <= W:
            ans = max(ans,i)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    INF = 10**9
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for _ in range(N)]
    sumv = sum([v for w,v in wv])
    dp = [[INF]*(sumv+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(sumv+1):
            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] = dp[i][j]
    ans = 0
    for i in range(sumv+1):
        if dp[N][i] <= W:
            ans = max(ans,i)
    print(ans)
    print(dp)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

W,V=[],[]
V_max=0
for i in range(n):
 a,b=map(int,input().split())
 W.append(a)
 V.append(b)
 V_max=max(V_max,b)

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

dp[0][0]=0

for i in range(n):
 for sum_v in range(n*V_max):

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

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

ans=0
for i in range(n*V_max+1):
 if dp[-1][i]<=w:
  ans=max(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)
BIG = 10**15+1
LEN = 10**3
LEN = LEN*N
dp = [[BIG for i in range(LEN)]for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0

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

ans = 0
for j in range(LEN):
    if dp[N][j] <= W and j >= ans:
        ans = j

        
print(ans)
# print(dp)

Submission status: Wrong Answer

Solution code:
def solve():
    N, W = map(int, input().split())
    MAX_V = 100
    MAX_N = 110
    w = []
    v = []
    for i in range(N):
        tmpw, tmpv = map(int, input().split())
        w.append(tmpw)
        v.append(tmpv)

    dp = [[float('inf') for i in range(MAX_V+1)] for j in range(MAX_N+1)]

    dp[0][0] = 0

    for i in range(N):
        for sum_v in range(MAX_V):
            if sum_v - v[i] >= 0:
                dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i])
            
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
        
    res = 0
    for sum_v in range(MAX_V+1):
        if dp[N][sum_v] <= W:
            res = sum_v
    print(res)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
#貰うDP
#PyPy必須？
n,w=map(int,input().split())
v=10**5
WV=[list(map(int,input().split())) for i in range(n)]
#dp[i][v] 価値vでの最低体重
dp=[[10**10]*(v+1) for i in range(n+1)]
for j in range(n):
    dp[j][0]=0
for j in range(v+1):
    dp[1][j]=((j+WV[0][1]-1)//WV[0][1])*WV[0][0]
for i in range(1,n):
    for j in range(v+1):
        if j-WV[i][1]>=0 and j-WV[i][1]<=v:
            dp[i+1][j]=min(dp[i][j-WV[i][1]]+WV[i][0], dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
print(bisect_right(dp[n], w)-1)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
wv=[[int(i) for i in input().split()]for _ in range(n)]
dp=[10**5+1]*(10**5+1)
dp[0]=0
for i in range(0,n):
    w,v = wv[i]
    for j in range(10**5,v-1,-1):
        dp[j]=min(dp[j],dp[j-v]+w)
for i in range(10**5,-1,-1):
    if dp[i]<=W:
        print(i)
        break

Submission status: Wrong Answer

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())
V = sum(v)

dp = [[float("inf")] * (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] >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i])
        else:
            dp[i+1][j] = dp[i][j]

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

Submission status: Wrong Answer

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())
V = sum(v)

dp = [[float("inf")] * (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] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]]+w[i])
        else:
            dp[i+1][j] = dp[i][j]

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

Submission status: Wrong Answer

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())
V = sum(v)

dp = [[float("inf")] * (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] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]]+w[i])
        else:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

Submission status: Wrong Answer

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())
V = sum(v)

dp = [[float("inf")] * (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] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]]+w[i])
        else:
            dp[i+1][j] = dp[i][j]

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

Submission status: Wrong Answer

Solution code:
#計算量的にはきつそうだけど，dp[i][j]でやる？

s=input()
t=input()

ls=len(s)
lt=len(t)

add=ls-lt
if add>0:
    t+="T"*add
else:
    s+="S"*(-1*add)
N=len(s)
    
    
#sのi文字目とtのj文字目までで取れる最長部分列
dp=[[""]*(N+1) for _ in range(N+1)]

temp=["",""]

for i in range(N):
    for j in range(N):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+s[i]
            L=len(dp[i+1][j+1])
        else:
            temp[0]=dp[i+1][j]
            temp[1]=dp[i][j+1]
            if len(temp[0])>len(temp[1]):
                dp[i+1][j+1]=temp[0]
            else:
                dp[i+1][j+1]=temp[1]

                    
print(dp)

Submission status: Wrong Answer

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

M=sum(v)
#i番目までの商品で価値の総和をjにしたときの重さ（W以下の範囲で）
dp=[[-1]*(M+1) for _ in range(N+1)]

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

print(ans)

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
data = []
v_sum = 0
inf = 10**3
for i in range(n):
    data.append(list(map(int, input().split())))
    v_sum += data[i][1]

dp = [[inf for i in range(v_sum+1)] for j in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
    weight, v = data[i-1]
    for j in range(v_sum+1):
        if j - v >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v] + weight)
        else:
            dp[i][j] = dp[i-1][j]
ans = 0
for i in range(v_sum+1):
    if dp[-1][i] <= w:
        ans = max(ans, i)
print(ans)

Submission status: Wrong Answer

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

@author: matsui
"""


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

M=int(sum(vi))
dp1=[sum(wi)+1]*(M+1)
#dp2=[sum(wi)+1]*(M+1)
dp1[0]=0
   
#L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in zip(wi,vi):
    s+=v
    for j in range(min(s,M),v-1,-1):
        if j >= v: 
            if dp1[j] > dp1[j-v]+w: dp1[j]=dp1[j-v]+w
        if dp1[j] > dp1[j]: dp1[j]=dp1[j]
    print(dp1)
    #print(dp2)
    #dp1=[dp2[i] for i in range(M+1)]    
    
#print(max(dp))
m=0
for i in range(M+1):
    if dp1[i]<=W:
        m=i
print(m)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
WV = []
for i in range(N):
    WV.append(list(map(int,input().split())))
dp = [[float('inf') for j in range(100001)] for i in range(N)]
dp[0][0] = 0
for i in range(N):
    w,v = WV[i]
    if i == 0:
        for j in range(100001):
            if j-v >= 0:
                dp[i][j] = min(dp[i][j],dp[i][j-v]+w)
    else:
        for j in range(100001):
            if j-v >= 0:
                dp[i][j] = min(dp[i-1][j-v]+w,dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]

ans = 0
for i,e in enumerate(dp[-1]):
    if W >= e:
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
items = sorted([list(map(int, input().split())) for i in range(N)])
V = 10**3

dp = [[float("inf")]*(N + 1) for i in range(V + 1)]
dp[0] = [0]*(N + 1)
for i in range(V + 1):
    for j in range(N):
        k = i - items[j][1]
        dp[i][j + 1] = min(dp[i][j + 1], dp[i][j])
        if k < 0:
            break
        else:
            dp[i][j + 1] = min(dp[i][j + 1], dp[k][j] + items[j][0])

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np

N,W = map(int,input().split())
item = []
V_MAX = 0
for _ in range(N):
    w, v = map(int,input().split())
    V_MAX += v
    item.append([w,v])
dp = np.array([float('inf')]*(V_MAX+1))
dp[0] = 0
pos = np.array([0]*(V_MAX+1))
pos[0] = 1
for w,v in item:
    dp = np.minimum(dp, np.concatenate([np.array([np.inf]*v),np.roll(dp,v)[v:]]) + np.dot(np.concatenate([np.zeros(v),np.roll(pos,v)[v:]]),w))
    pos = (pos + np.concatenate([np.zeros(v),np.roll(pos,v)[v:]]))

res = 0
for i in range(V_MAX + 1):
    if dp[i]<=W and res < i : res = i
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np

def solver():
    N,W = map(int,input().split())
    item = []
    V_MAX = 0
    for _ in range(N):
        w, v = map(int,input().split())
        V_MAX += v
        item.append([w,v])
    dp = np.array([float('inf')]*(V_MAX+1))
    dp[0] = 0
    pos = np.array([0]*(V_MAX+1))
    pos[0] = 1
    for w,v in item:
        dp = np.minimum(dp, np.concatenate([dp[:v],np.roll(dp,v)[v:]]) + np.dot(np.concatenate([pos[:v],np.roll(pos,v)[v:]]),w))

        pos = (pos + np.concatenate([np.zeros(v),np.roll(pos,v)[v:]]))

    res = 0
    for i in range(V_MAX + 1):
        if dp[i]<=W and res < i : res = i
    print(res)
solver()

Submission status: Wrong Answer

Solution code:
import numpy as np

N, W = map(int, input().split())
v_max = 10**3

dp = np.ones(v_max*N, dtype=int) * (10**9+1)
dp[0] = 0

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


print(np.where(dp <= W)[0][-1])

Submission status: Wrong Answer

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

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

f_inf = float('inf')
max_v = 10000

dp = [f_inf]*(max_v+10)
dp[0] = 0

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

ans = 0
for i in range(max_v+1):
    if dp[i] <= max_w:
        ans = max(ans, i)
print(ans)

Submission status: Wrong Answer

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

INF = float('inf')
ww = [0]*n
vv = [0]*n
vm = 5
dp = [[INF]*(n*vm+1) for _ in range(n+1)]

for i in range(n):
  ww[i],vv[i] = map(int,input().split())      


for i in range(1,n+1):
  dp[i][0] = 0
  for j in range(1,n*vm+1):        
    if j < vv[i-1]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-vv[i-1]] + ww[i-1])        

ans = 0
for i in range(n*vm+1):
  if dp[n][i]<=w:
    ans = i
print(ans)

Submission status: Wrong Answer

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

dp = [[10**9]*(max(lstV)*N+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(max(lstV)*N+1):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if dp[i][j] + lstW[i] <= W:
            dp[i+1][j+lstV[i]] = min(dp[i+1][j+v], dp[i][j]+lstW[i])
ans = []
for i in range(max(lstV)*N+1):
    if dp[N-1][i] <= W:
        ans.append(i)
print(max(ans))

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
lstW = [0]
lstV = [0]
for i in range(N):
    w, v = map(int, input().split())
    lstW.append(w)
    lstV.append(v)

dp = [[10**9]*(max(lstV)*N+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    for j in range(1, max(lstV)*N+1):
        if j - lstV[i] >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-lstV[i]]+lstW[i])
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j])
ans = []
for i in range(1, max(lstV)*N+1):
    if dp[N][i] <= W:
        ans.append(i)
print(max(ans))

Submission status: Wrong Answer

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

V = sum(v)
dp = [[2**60]*(V+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j - v[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j],dp[i][j-v[i]]+w[i])
        else:
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
ans = 0
for j in range(V+1):
    if dp[N][j] <= W:
        ans = j
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
MV = (10**3)*N+1
MV = 100
dp = [[0] + [10**18]*(MV-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(1, MV):
        dp[i][j] = min(dp[i-1][j], dp[i-1][max(0, j-v)]+w)
for i in range(MV):
    if dp[N][MV-i-1] <= W:
        print(MV-i-1)
        break
#print(dp[N][W])

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

for i in range(N):
    for j in range(N * vmax):
        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 j in range(1, N*vmax):
    if dp[N][N*vmax - j] <= W:
        print(N*vmax - j)
        break

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
INF = float("inf")


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):

    DP = defaultdict(int)
    DP[0] = 0

    for i in range(N):
        # print(DP)
        DPnew = defaultdict(int)
        for key in DP:
            DPnew[key+w[i]] = max(DP[key] + v[i], DPnew[key+w[i]])
            DPnew[key] = DP[key]
        DP = DPnew.copy()
    ans = 0
    for key in DP:
        if key <= W:
            ans = max(ans, DP[key])
    print(ans)
    return


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))
    solve(N, W, w, v)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

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

# pdb.set_trace()

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

# print(Weight)
print(value_max)

Submission status: Wrong Answer

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

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

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

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

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

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

# print(Weight)
print(value_max)
# pdb.set_trace()

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
items=[]
dp=[0 for i in range(w+1)]
for i in range(n):
    wi,vi=map(int,input().split())
    for j in range(w-wi+1):
        dp[j+wi]=max(dp[j+wi],dp[j]+vi)
print(max(dp))

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
INF = float('inf')
MAX_V = 10 ** 3

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import collections


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


def main():
    N, W = [int(i) for i in input().split()]
    items = [Item(int(i), int(j)) for (i, j) in [input().split() for _ in range(N)]]
    MAX_V = 10**3 * N
    # dp[n][v] = 品物の選択肢を先頭からn個にしたとき、価値v以上にするための最小の重さ（infで初期化）
    dp = [[float('inf')] * (MAX_V + 1) for _ in range(N + 1)]
    dp[0][0] = 0

    for n in range(N):
        # n番目の品物 (n = 0, 1, 2...)
        item = items[n]
        # 選択肢をn + 1個にしたとき
        for v in range(MAX_V + 1):
            # n番目の品物を選ぶ場合
            # v < item.value のときは、この品物を選んでしまうとvが増えてしまうので選べない
            if v - item.value >= 0:
                dp[n + 1][v] = min(dp[n + 1][v], dp[n][v - item.value] + item.weight)
            # n番目の品物を選ばない場合
            dp[n + 1][v] = min(dp[n + 1][v], dp[n][v])

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
INF=10**9+1
import numpy as np
dp=np.full(10*5+1,INF,dtype=int)
dp[0]=0
for i in range(N):
  w,v=map(int,input().split())
  np.minimum(dp[:-v]+w,dp[v:],out=dp[v:])

for i in range(len(dp)-1,-1,-1):
  if dp[i]<=W:
    print(i)
    break

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
INF=10**9+1
import numpy as np
dp=np.full(1001,INF,dtype=int)
dp[0]=0
for i in range(N):
  w,v=map(int,input().split())
  np.minimum(dp[:-v]+w,dp[v:],out=dp[v:])

for i in range(len(dp)-1,-1,-1):
  if dp[i]<=W:
    print(i)
    break

Submission status: Wrong Answer

Solution code:
INF = float("inf")


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

    # dp[0..N][value]: weight
    dp = [[INF for i in range(1000 * 100 + 1)] for _ in range(N + 1)]
    dp[0][0] = 0

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

        for v in range(1000 * 100 + 1):
            if value <= v:
                dp[n + 1][v] = min(dp[n][v - value] + weight, dp[n][v])
            else:
                dp[n + 1][v] = dp[n][v]

    ans = [0]
    for v in range(100 * 100 + 1):
        if dp[N][v] <= W:
            ans.append(v)

    print(max(ans))


main()

Submission status: Wrong Answer

Solution code:
INF = float("inf")


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

    # dp[0..N][value]: weight
    dp = [[INF for i in range(1000 * 100 + 1)] for _ in range(N + 1)]
    dp[0][0] = 0

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

        for v in range(1000 * 100 + 1):
            if value <= v:
                dp[n + 1][v] = min(dp[n][v - value] + weight, dp[n][v])
            else:
                dp[n + 1][v] = dp[n][v]

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


main()

Submission status: Wrong Answer

Solution code:
INF = float("inf")


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

    # dp[0..N][value]: weight
    dp = [[0 if i == 0 else INF for i in range(1000 * 100 + 1)]
          for _ in range(N + 1)]

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

        for v in range(1000 * 100 + 1):
            if value <= v:
                dp[n + 1][v] = min(dp[n][v - value] + weight, dp[n][v])
            else:
                dp[n + 1][v] = dp[n][v]

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


main()

Submission status: Wrong Answer

Solution code:
INF = float("inf")


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

    # dp[0..N][value]: weight
    dp = [[0 if i == 0 else INF for i in range(1000 * 100 + 1)]
          for _ in range(N + 1)]

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

        for v in range(1, 1000 * 100 + 1):
            if value <= v:
                dp[n + 1][v] = min(dp[n][v - value] + weight, dp[n][v])
            else:
                dp[n + 1][v] = dp[n][v]

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


main()

Submission status: Wrong Answer

Solution code:
INF = 99999999999999


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

    # dp[0..N][value]: weight
    dp = [[0 if i == 0 else INF for i in range(1000 * 100 + 1)]
          for _ in range(N + 1)]

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

        for v in range(1, 1000 * 100 + 1):
            if value <= v:
                dp[n + 1][v] = min(dp[n][v - value] + weight, dp[n][v])
            else:
                dp[n + 1][v] = dp[n][v]

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


main()