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^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

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

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 2

5000000000

The answer may not fit into a 32-bit integer type.

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())
k=[[0,0] for i in range(N)]
dp=[[0]*(W+1) for j in range(N+1)]
for i in range(N):
    k[i][0],k[i][1]=map(int,input().split())



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


print(dp)

Submission status: Wrong Answer

Solution code:
def solve(ls, n, w):
	dp = [0] * (w + 1)
	for i in range(1, w + 1):
		for j in range(n):
			if i - ls[j][0] >= 0:
				dp[i] = max(dp[w - ls[j][0]] + ls[j][1], dp[i])
			else:
				dp[i] = dp[i - 1]
	return dp[w]


n, w = map(int, input().split())
ls = []
for i in range(n):
	ls.append(list(map(int, input().split())))
print(solve(ls, n, w))

Submission status: Wrong Answer

Solution code:
def knapsack_dp(n,w,wts,val):
    dp=[[0]*(w+1) for i in range(n+1)]

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

    return dp[n][w]


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

print(knapsack_dp(n,w,wts,vals))

Submission status: Wrong Answer

Solution code:
#4
N,W=map(int,input().split())
A=[[0]]+[[int(x) for x in input().split()] for i in range(N)]

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

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

Submission status: Wrong Answer

Solution code:
#4
N,W=map(int,input().split())
A=[[0]]+[[int(x) for x in input().split()] for i in range(N)]

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

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

Submission status: Wrong Answer

Solution code:
#DP D
def main():
    import sys
    N, W = map(int, sys.stdin.readline().split())
    L = tuple([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)])
    #print(L)
    dp = [[0 for i in range(10**5+1)] for _ in range(N)]
    for i in range(N):
        w, v = L[i][0], L[i][1]
        if i>=1:
            dp[i][w] = max(v, dp[i-1][w])
        elif i==0:
            dp[i][w] = v
        for j in range(10**5+1):
            if i>=1 and w+j <=10**5 and dp[i-1][j]!=0:
                dp[i][j] = max(dp[i-1][j], dp[i][j])
                dp[i][w+j] = max(dp[i-1][w+j], v + dp[i-1][j])
                
    print(max(dp[-1][:W+1]))



if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
#DP D
def main():
    import sys
    N, W = map(int, sys.stdin.readline().split())
    L = tuple([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)])
    print(L)
    dp = [[0 for i in range(10**5+1)] for _ in range(N)]
    for i in range(N):
        w, v = L[i][0], L[i][1]
        if i>=1:
            dp[i][w] = max(v, dp[i-1][w])
        elif i==0:
            dp[i][w] = v
        for j in range(10**5+1):
            if i>=1 and w+j <=10**5 and dp[i-1][j]!=0:
                dp[i][j] = max(dp[i-1][j], dp[i][j])
                dp[i][w+j] = max(dp[i-1][w+j], v + dp[i-1][j])
                
    print(max(dp[-1][:W+1]))



if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

def rec(i,w,v):
    if DP[i][w] != 0:
        return DP[i][w]
    if i == N:
        return v
    if w == 0:
        return v
    else:
        res = rec(i+1,w,v)
        if w-WV[i][0] >= 0:
            res = max(res,rec(i+1,w-WV[i][0],v+WV[i][1]))
        DP[i][w] = res
        return DP[i][w]

rec(0,W,0)
ans = 0
for dp in DP:
    ans = max(max(dp),ans)

print(ans)

Submission status: Wrong Answer

Solution code:
NW = list(map(int,input().split()))
N,W = NW[0],NW[1]
wv = [map(int,input().split()) for _ in range(N)]
w,v = [list(i) for i in zip(*wv)]
dp = [[0]*(W+1) for _ in range(N+1)]#初期値は入力済み
ans = 0
for i in range(1,N+1):
    for j in range(1,W+1):
        if j-w[i-1] < 0:
            dp[i][j] = dp[i-1][j]
            ans = max(ans,dp[i][j])
        else:
            dp[i][j] = max(dp[i-1][j-w[i-1]]+v[i-1],dp[i-1][i])
            ans = max(ans,dp[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(N-1):
  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: Wrong Answer

Solution code:
def dynamic():
  N, W = map(int, input().split())
  wv = [list(map(int, input().split())) for _ in range(N)]
  
  dp = [[0]*(W + 1)]*(N + 1)
  
  for i in range(N):
    w = wv[i][0]
    v = wv[i][1]
    for sum_w in range(W+1):
      
      if sum_w - w >= 0:
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w] + v)
        
      dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])  
      
  
  return dp[N][W]

print(dynamic())

Submission status: Wrong Answer

Solution code:
n,wmax = map(int,input().split())
dp = [[0 for ww in range(wmax+1)] for i in range(n+1)]

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

print(dp[0][0]+2)

for i in range(n):
    for ww in range(wmax+1):
        dp[i+1][ww] = dp[i][ww] if w[i]>ww else max(dp[i][ww], dp[i][ww-w[i]]+v[i])

ans = dp[n][wmax]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()

def main():

    # i have too make index as weight and value as value
    import numpy as np
    N, W = map(int, input().split())

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

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


    print(dp)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
D = {0: 0}
for i in range(N):
  w, v = map(int, input().split())
  X = [[j, D[j]] for j in D]
  for j in X:
    if j[0] + w <= W:
      if j[0] + w in D:
        D[j[0]+w] = max(D[j[0]] + v, D[j[0]+w])
      else:
        D[j[0]+w] = D[j[0]] + v
print(max(D[i] for i in D))

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
DF = {0: 0}
DS = {0: 0}
for i in range(N//2):
  w, v = map(int, input().split())
  X = [[j, DF[j]] for j in DF]
  for j in X:
    if j[0] + w <= W:
      if j[0] + w in DF:
        DF[j[0]+w] = max(DF[j[0]] + v, DF[j[0]+w])
      else:
        DF[j[0]+w] = DF[j[0]] + v
for i in range(N//2, N):
  w, v = map(int, input().split())
  X = [[j, DS[j]] for j in DS]
  for j in X:
    if j[0] + w <= W:
      if j[0] + w in DS:
        DS[j[0]+w] = max(DS[j[0]] + v, DS[j[0]+w])
      else:
        DS[j[0]+w] = DS[j[0]] + v
LF = [j for j in DF]
LS = [j for j in DS]
VS = [0 for _ in DS]
m, n = len(LF), len(LS)
tmp = n
cnt = 0
while tmp != 0:
  cnt += 1
  tmp //= 2
VS[0] = DS[0]
for i in range(1, n):
  VS[i] = max(VS[i-1], DS[LS[i]])
LF.sort()
LS.sort()
M = 0
for i in LF:
  l, r = 0, n
  d = (l + r) // 2
  for _ in range(cnt+1):
    if LS[d] <= W - i:
      l = d
      d = (l + r) // 2
    else:
      r = d
      d = (l + r) // 2
  if VS[d] + DF[i] > M:
    M = VS[d] + DF[i]
print(M)

Submission status: Wrong Answer

Solution code:
# 初期入力
N,W = (int(x) for x in input().split())
W_V = [list(map(int, input().split())) for i in range(N)]

#価値でソート
W_V_sorted = sorted(W_V,key=lambda x:x[1],reverse=True)

#ナップザックに入れる
v_sum = 0
w_sum = 0
for w_v in W_V_sorted:
    if w_sum + w_v[0] <= W: # 入れても重量内なら
        v_sum += w_v[1]
        w_sum += w_v[0]  


print(v_sum)

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    N, W = map(int, input().split())
    dp = [0] * (W+1)

    for i in range(N):
        weight, value = map(int, input().split())
        # for w in range((W - weight)+1):
        for w in range((W - weight), -1, -1):
            dp[w + weight] = max(dp[w + weight], dp[w] + value)

        # dp = new_dp

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











"""
6 15
6 5
5 6
6 4
6 6
3 5
7 2


3 8
3 30
4 50
2 60
"""

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    N, W = map(int, input().split())
    dp = [0] * (W+1)

    for i in range(N):
        weight, value = map(int, input().split())
        for w in range((W - weight)+1):
        # for w in range((W - weight), -1, -1):
            dp[w + weight] = max(dp[w + weight], dp[w] + value)

        # dp = new_dp

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











"""
6 15
6 5
5 6
6 4
6 6
3 5
7 2


3 8
3 30
4 50
2 60
"""

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    n,w = map(int, input().split())
    ary = [list(map(int, stdin.readline().split())) for _ in range(n)]
    dp = [[0 for _ in range(w+1)] for _ in range(n)]
    for i in range(n-1):
        for y in range(w+1):
            dp[i+1][y] = dp[i][y-ary[i+1][0]] + ary[i+1][1] if ary[i+1][0] <= y else dp[i][y]
    print(dp[n-1][w])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
weight = []
value = []
for i in range(N):
    a,b = map(int,input().split())
    value.append(a)
    weight.append(b)
dp =[[0 for i in range(W+1)] for t in range(N+1)]
for i in range(0,N):
    for w in range(W+1):
        if weight[i]<= w:
            dp[i+1][w] = max((dp[i][w-weight[i]]+value[i]),dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

Submission status: Wrong Answer

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

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

print(max(dp[-1]))

Submission status: Wrong Answer

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

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

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

print(dp[-1])

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)

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

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

print(dp[N][W])

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)

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

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

print(dp[N][W])

Submission status: Wrong Answer

Solution code:
def main():
    n, w= map(int, input().split())
    w_item = []
    v_item = []
    dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
    for _ in range(n):
        tmp_w, tmp_v = map(int, input().split())
        w_item.append(tmp_w)
        v_item.append(tmp_v)

    for i in range(n):
        for j in range(w+1):
            if w_item[i] <= j:
                dp[i+1][j] = max(dp[i][j], dp[i][j-w_item[i]] + v_item[i])
            else:
                dp[i+1][j] = dp[i][j]
    print(dp)

if __name__ == '__main__':
    main()

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())
    
INF = 10 ** 15
dp = [[INF]*(10**5+1) for _ in range(n+1)]
dp[0][0] = 0

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

max_v =0
for sum_v in range(10**5+1):
    if dp[n][sum_v] <= W:
        max_v = sum_v

print(max_v)

Submission status: Wrong Answer

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

x, y  = map(int, input().split())
li =[]
for i in range(x):
    l = list(map(int, input().split()))
    li.append(l)
dp = [[0]*(y+1) for _ in range(x+1)]
for i in range(x):
    for j in range(1, y+1):
        if j - li[i][0] >= 0:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j - li[i][0] ]+ li[i][1])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[x][y])

Submission status: Wrong Answer

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

def solve(n, w ,weights, values):
    def rec_solve(cw, cv, max_w, i):
        nonlocal weights, values
        #print(cw, cv, i)
        if i == -1:
            return cv
        
        # take
        if weights[i] + cw <= max_w:
            return max(rec_solve(cw+weights[i], cv + values[i], max_w, i-1),
                        rec_solve(cw, cv, max_w, i-1))

        else:
            # dont take
            return rec_solve(cw, cv, max_w, i-1)

    return rec_solve(0, 0, w, n-1)

def solve_fast(n_items, max_w, weights, values):
    dp =  [[0]*(max_w+1) for _ in range(n_items)]
    dp[0] = [values[0] if i >= weights[0] else 0 for i in range(max_w+1)]

    for r in range(1, n_items):
        cw, cv = weights[r], values[r]
        for c in range(max_w+1):
            if cw > c:
                dp[r][c] = dp[r-1][c]
            else:
                dp[r][c] = max(cv, dp[r-1][c-cw] + cv)

    #for r in dp:
        #print(r)

    return dp[-1][-1]


print(solve_fast(N, W, weights, values))

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
cost=[[0 for i in range(w)] for i in range(n)]
value=[tuple(map(int,input().split())) for i in range(n)]
for i in range(n):
  for j in range(w):
    weight_=value[i][0]
    value_=value[i][1]
    if weight_+j>n-1:break
    if j < weight_:
      cost[i][j]=cost[i-1][j]
    else:
      cost[i][j]=max(cost[i-1][j-weight_]+value_,cost[i-1][j])
print(max(cost[-1]))

Submission status: Wrong Answer

Solution code:
def resolve():
    N, W = map(int, input().split())
    wv = []
    for i in range(N):
        wv.append([int(i) for i in input().split()])
    dp = [[0 if wv[0][0] > i else wv[0][1] for i in range(W + 1)]]
    for i in range(N):
        dp.append(
            [
                dp[-1][w]
                if w < wv[i][0]
                else max(dp[-1][w - wv[i][0]] + wv[i][1], dp[-1][w])
                for w in range(W + 1)
            ]
        )
    print(dp[-1][-1])


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

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

wv.sort()

ans = 0
dp = np.zeros(W, dtype=int)

for w, v in wv:
    np.maximum(dp[:-w] + v, dp[w:], out = dp[w:])

ans = dp[-1]
print(ans)

Submission status: Wrong Answer

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


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    weights = defaultdict(int)
    weights[0] = 0
    costs = set([0])
    for i in range(N):
        newCosts = set()
        for c in costs:
            nc = c + w[i]
            if nc > W:
                continue
            newCosts.add(nc)
            weights[nc] = max(weights[nc],weights[c]+v[i])
        costs = costs|newCosts
    print(max(weights.values()))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    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().rstrip().split(" "))
wv = [[0,0,0] for _ in range(N)]
ans = [0,0]
for i in range(N):
  p = list(map(int,input().rstrip().split(" ")))
  wv[i][1] = p[0]
  wv[i][2] = p[1]
  wv[i][0] = p[1] / p[0]
wv.sort()
wv.reverse()
for i in range(N):
  if wv[i][1] + ans[0] < W:
    ans[0] += wv[i][1]
    ans[1] += wv[i][2]
print(ans[1])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,w=map(int,input().split())
dp=[[0]*w for _ in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  for j in range(w):
    if i==0:
      if j>a-2:dp[i][j]=b
    elif j>a-2:
      if j==a-1:dp[i][j]=max(b,dp[i-1][j])
      else:dp[i][j]=max(dp[i-1][j-a]+b,dp[i-1][j])
    else:dp[i][j]=dp[i-1][j]
print(dp[n-1][n-1])

Submission status: Wrong Answer

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

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

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

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

for i in dp:
    print(i)

Submission status: Wrong Answer

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

# dp[i][j] : i番目までで、総重量jの時の最大価値
dp = [[0]*(w+1) for _ in range(n)]
for i in range(n):
    wi,vi = wv[i]
    for j in range(w+1):
        if wi<=j:
            dp[i][j] = max(dp[i][j], dp[i-1][j-wi]+vi)
        else:
            dp[i][j] = dp[i-1][j]

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

Submission status: Wrong Answer

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

def main():
    N, W = map(int, input().split())
    wv = list(map(int, input().split()) for _ in range(N))
    
    dp = [0] * (W + 1)
    
    for w, v in wv:
        for i in range(W, w, -1):
            dp[i] = max(dp[i], dp[i - w] + v)
    
    print(dp[-1])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np


def DP(i, X, w, v, memo):
    if (X < 0):
        return -10 ** 9
    if (memo[i, X] != -10 ** 9):
        return memo[i, X]
    result = max(DP(i + 1, X, w, v, memo),
                 DP(i + 1, X - w[i], w, v, memo) + v[i])
    memo[i, X] = result
    return result


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())
MINUS_INF = -10 ** 9
memo = np.full((N + 1, W + 1), MINUS_INF)
memo[N, :] = 0
answer = DP(0, W, w, v, memo)
print(answer)

Submission status: Wrong Answer

Solution code:
#d
n,W=map(int,input().split())
w=[0]
v=[0]
for i in range(n):
    x,y=map(int,input().split())
    w.append(x)
    v.append(y)

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

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

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)

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

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

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
d = {}
p = []
for i in range(n):
    k,v = map(int,input().split())
    d[k] = v
    p.append(k)

dp = []
for i in range(n+1):
    o = []
    for j in range(w+1):
        o.append(0)

    dp.append(o)


for i in range(n):
    for j in range(w+1):
        if p[i] > j:
            dp[i+1][j] = dp[i][j]

        else:
            dp[i+1][j] = max(d[p[i]] + dp[i][j - p[i]], dp[i][j])

print(dp[n][w])

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
d = {}
p = []
for i in range(n):
    k,v = map(int,input().split())
    d[k] = v
    p.append(k)

dp = []
for i in range(n+1):
    o = []
    for j in range(w+1):
        o.append(0)

    dp.append(o)


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

        else:
            dp[i+1][j] = max(d[p[i]] + dp[i][j - p[i]], dp[i][j])

print(dp[n][w])

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
d = {}
p = []
for i in range(n):
    k,v = map(int,input().split())
    d[k] = v
    p.append(k)

dp = []
for i in range(n+1):
    o = []
    for j in range(w+1):
        o.append(0)

    dp.append(o)


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

        else:
            dp[i+1][j] = max(d[p[i]] + dp[i][j - p[i]], dp[i][j])

print(dp[n][w])

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
d = {}
p = []
for i in range(n):
    k,v = map(int,input().split())
    d[k] = v
    p.append(k)

l = []
for i in range(n+1):
    o = []
    for j in range(w+1):
        o.append(0)

    l.append(o)

# MAIN DP MATRIX OPERATION
for i in range(1,n+1):
    for j in range(1,w+1):
        if p[i-1] > j:
            l[i][j] = l[i-1][j]

        else:
            l[i][j] = max(d[p[i-1]] + l[i-1][j-p[i-1]],l[i-1][j])


print(max(l[n]))

Submission status: Wrong Answer

Solution code:
# 埋める配列
# dp[i][w] : i番目までのお菓子で、重さの総和がw以下となる選び方の最大値

# 計算方法
# dp[0][j] = 0
# dp[i][j] = max(dp[i - 1][j],              #i番目のお菓子を使わないパターン
#               dp[i - 1][j - wi] + vi)     #i番目のお菓子を使ったパターン

# 埋める順序
# iが小さい順、jは好きな順

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

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

for i in range(1, N + 1):
    wi, vi = wv[i - 1]
    for j in range(W + 1):
        if j - wi >= 0:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wi] + vi)

answer = -1
for d in dp:
    answer = max(answer, max(d))
print(answer)

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
d = {}
p = []
for i in range(n):
    k,v = map(int,input().split())
    d[k] = v
    p.append(k)

l = []
for i in range(n+1):
    o = []
    for j in range(w+1):
        o.append(0)

    l.append(o)

# MAIN DP MATRIX OPERATION
for i in range(1,n+1):
    for j in range(1,w+1):
        if p[i-1] > j:
            l[i][j] = l[i-1][j]

        else:
            l[i][j] = max(d[p[i-1]] + l[i-1][j-p[i-1]],l[i-1][j])


print(l[n][w])

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
d = {}
p = [0]
for i in range(n):
    k,v = map(int,input().split())
    d[k] = v
    p.append(k)

l = []
for i in range(n+1):
    o = []
    for j in range(w+1):
        o.append(0)

    l.append(o)

# MAIN DP MATRIX OPERATION
for i in range(1,n+1):
    for j in range(1,w+1):
        if p[i] > j:
            l[i][j] = l[i-1][j]

        else:
            l[i][j] = max(d[p[i]] + l[i-1][j-p[i]],l[i-1][j])


print(l[n][w])

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
d = {}
p = [0]
for i in range(n):
    k,v = map(int,input().split())
    d[k] = v
    p.append(k)

l = []
for i in range(n+1):
    o = []
    for j in range(w+1):
        o.append(0)

    l.append(o)

# MAIN DP MATRIX OPERATION
for i in range(1,n+1):
    for j in range(0,w+1):
        if p[i] > j:
            l[i][j] = l[i-1][j]

        else:
            l[i][j] = max(d[p[i]] + l[i-1][j-p[i]],l[i-1][j])
            #l[i][j] = max(d[p[i]] + l[i - 1][j - p[i]], l[i - 1][j])

#print(l)
print(l[n][w])

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
from collections import defaultdict
n,w=map(int,stdin.readline().split())
d=defaultdict(int)
l1,l2=[],[]
for i in range(n):
    ww,v=map(int,stdin.readline().split())
    l1.append(ww)
    l2.append(v)
l3,l4=[l1[0]],[l2[0]]
for i in range(1,n):
    for j in range(len(l3)):
        if l1[i]+l3[j]<=w:
            l3.append(l1[i]+l3[j])
            l4.append(l2[i]+l4[j])
            d[l1[i]+l3[j]]=max(d[l1[i]+l3[j]],l2[i]+l4[j])
    l3.append(l1[i])
    l4.append(l2[i])
    d[l1[i]]=max(d[l1[i]],l2[i])
l3.sort()
val=0
for i in l3:
    if i>w:
        break
    val=max(val,d[i])
print(val)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N,w = [int(x) for x in input().split()]
ll = []
for i in range(N):
    abc = [int(x) for x in input().split()]
    ll.append(abc)
DP = [[0]*(w+1) for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,w+1):
        if ll[i-1][0] <= j:
            DP[i][j] = max(DP[i-1][j-ll[i-1][0]]+ll[i-1][1],DP[i-1][j])
        else:
            DP[i][j] = DP[i-1][j]
print(DP)

Submission status: Wrong Answer

Solution code:
n,w = map(int, input().split())
lst_weight = [0 for _ in range(n)]
lst_value = [0 for _ in range(n)]
for i in range(n):
    lst_weight[i], lst_value[i] = map(int, input().split())
dp = [[0 for i in range(w+1)] for j in range(n+1)]

#後者が前者よりも大きい時に更新→DPテーブルを-infに初期化
def chmax(a,b):
    if(a< b):
        return b
    else:
        return a

#各品物の選択
for i in range(n):
    for sum_w in range(w+1):
        #選択した品物を加える
        if sum_w >= lst_weight[i]:
            #今回の手の暫定最大値と1つ前までの手の確定最大値を比較する
            dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w-lst_weight[i]] + lst_value[i])
        else:
            # i番目の品物を選ばない→前までの手で最適化されている最大値が次の手の最大値になるはず
            dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w])
            
print(dp[n][w])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N, W = map(int, input().split())
dp_w = np.zeros(N+1, dtype = int)
dp_v = np.zeros(N+1, dtype = int)
for i in range(N):
  w, v = map(int, input().split())
  if i == 0:
    dp_w[1] = w
    dp_v[1] = v
  else:
    for j in range(i+1):
      if dp_w[j] + w <= W:
        tmp_w = dp_w[j] + w
        tmp_v = dp_v[j] + v
        if tmp_v > dp_v[j+1]:
          dp_v[j+1] = tmp_v
          dp_w[j+1] = tmp_w
        if tmp_v == dp_v[j+1]:
          dp_w[j+1] = min(tmp_w, dp_w[j+1])
print(dp_v[N])

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
numbers=[]
for _ in range(N):
    w,v=input().split()
    numbers.append([int(w),int(v)])
def chmax(a,b):
    if a>=b:
        return a
    else:
        return b
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for a in range(N+1):
    for sum_w in range(W+1):
        if sum_w-numbers[a-1][0]>=0:
            dp[a][sum_w]=chmax(dp[a][sum_w],dp[a-1][sum_w-numbers[a-1][0]]+numbers[a-1][1])
        dp[a][sum_w]=chmax(dp[a][sum_w],dp[a-1][sum_w])
print(max(dp[-1]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# edpc e dp

import itertools
from math import factorial
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
INF = 1 << 60
MOD = 10 ** 9 + 7

# ここから書き始める
N, W = map(int, input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]
for i in range(N):
    w[i], v[i] = map(int, input().split())
dp = [[0 for j in range(W + 1)] for i in range(N)]
for i in range(W + 1):
    if i == w[0]:
        dp[0][i] = v[0]
    else:
        dp[0][i] = 0
for i in range(1, N):
    for j in range(W + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= w[i]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i])
print(dp[-1][-1])