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: Time Limit Exceeded

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

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

for i in range(1, N+1):
    weight = WV[i-1][0]
    value = WV[i-1][1]
    for w in range(W+1):
        if w-weight<0:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w-weight]+value, dp[i-1][w])

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
# AtCoder DP Task D - Knapsack 1
def knapsack(target, W, V): # target=knapsack weight
    P = [[0] * (target + 1) for _ in range(len(V))]
    for vi in range(len(V)):
        row, prev = P[vi], P[vi - 1]
        for w in range(target + 1):
            if vi > 0:
                row[w] = prev[w] # same value without vi-th item
                if w >= W[vi]:
                    new = P[vi - 1][w - W[vi]] + V[vi]
                    if new > P[vi][w]: # most value
                        row[w] = new
            else:
                if w >= W[vi]:
                    row[w] = V[vi]
    return P[len(V) - 1][target]

def knapsack_rec(target, W, V): # target=knapsack weight
    P = [[-1] * (target + 1) for _ in range(len(V))]

    def rec(w, index):
        if index == 0 and w >= W[index]:
            return V[index]
        elif index > 0:
            if P[index][w] != -1:
                return P[index][w]
            r = rec(w, index - 1)
            if w >= W[index]:
                y = rec(w - W[index], index - 1) + V[index]
                r = r if r > y else y
            P[index][w] = r
            return r
        return 0

    ret = rec(target, len(V) - 1)
    return ret

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# AtCoder DP Task D - Knapsack 1
def knapsack(target, W, V): # target=knapsack weight
    P = [[0] * (target + 1) for _ in range(len(V))]
    for vi in range(len(V)):
        row, prev = P[vi], P[vi - 1]
        for w in range(target + 1):
            if vi > 0:
                row[w] = prev[w] # same value without vi-th item
                if w >= W[vi]:
                    new = P[vi - 1][w - W[vi]] + V[vi]
                    if new > P[vi][w]: # most value
                        row[w] = new
            else:
                if w >= W[vi]:
                    row[w] = V[vi]
    return P[len(V) - 1][target]

def knapsack_rec(target, W, V): # target=knapsack weight
#    P = [[-1] * (target + 1) for _ in range(len(V))]
    P = {}

    def rec(w, index):
        if index == 0 and w >= W[index]:
            return V[index]
        elif index > 0:
            if (index, w) in P: # P[index][w] != -1:
                return P[(index,w)]
            r = rec(w, index - 1)
            if w >= W[index]:
                y = rec(w - W[index], index - 1) + V[index]
                r = r if r > y else y
            P[(index,w)] = r
            return r
        return 0

    ret = rec(target, len(V) - 1)
    return ret

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    n, w = map(int, input().split())
    W, V = [], []
    for _ in range(n):
        weight, value = map(int, input().split())
        W.append(weight)
        V.append(value)
    ans = knapsack_rec(w, W, V)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# AtCoder DP Task D - Knapsack 1
def knapsack(target, W, V): # target=knapsack weight
    P = [[0] * (target + 1) for _ in range(len(V))]
    for vi in range(len(V)):
        row, prev = P[vi], P[vi - 1]
        for w in range(target + 1):
            if vi > 0:
                row[w] = prev[w] # same value without vi-th item
                if w >= W[vi]:
                    new = P[vi - 1][w - W[vi]] + V[vi]
                    if new > P[vi][w]: # most value
                        row[w] = new
            else:
                if w >= W[vi]:
                    row[w] = V[vi]
    return P[len(V) - 1][target]

def knapsack_rec(target, W, V): # target=knapsack weight
#    P = [[-1] * (target + 1) for _ in range(len(V))]
    P = {}

    def rec(w, index):
        if index == 0 and w >= W[index]:
            return V[index]
        elif index > 0:
            if (index, w) in P: # P[index][w] != -1:
                return P[(index,w)]
            r = rec(w, index - 1)
            if w >= W[index]:
                y = rec(w - W[index], index - 1) + V[index]
                r = r if r > y else y
            P[(index,w)] = r
            return r
        return 0

    ret = rec(target, len(V) - 1)
    return ret

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    n, w = map(int, input().split())
    W, V = [], []
    for _ in range(n):
        weight, value = map(int, input().split())
        W.append(weight)
        V.append(value)
    ans = knapsack(w, W, V)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# AtCoder DP Task D - Knapsack 1
def knapsack(target, W, V): # target=knapsack weight
    P = [[0] * (target + 1) for _ in range(len(V))]
    for vi in range(len(V)):
        row, prev = P[vi], P[vi - 1]
        for w in range(target + 1):
            if vi > 0:
                row[w] = prev[w] # same value without vi-th item
                if w >= W[vi]:
                    new = P[vi - 1][w - W[vi]] + V[vi]
                    if new > P[vi][w]: # most value
                        row[w] = new
            else:
                if w >= W[vi]:
                    row[w] = V[vi]
    return P[len(V) - 1][target]

def knapsack_rec(target, W, V): # target=knapsack weight
    P = [[-1] * (target + 1) for _ in range(len(V))]

    def rec(w, index):
        if index == 0 and w >= W[index]:
            return V[index]
        elif index > 0:
            if P[index][w] != -1:
                return P[index][w]
            r = rec(w, index - 1)
            if w >= W[index]:
                y = rec(w - W[index], index - 1) + V[index]
                r = r if r > y else y
            P[index][w] = r
            return r
        return 0

    ret = rec(target, len(V) - 1)
    return ret

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

n, w = map(int, input().split())
W, V = [], []
for _ in range(n):
    weight, value = map(int, input().split())
    W.append(weight)
    V.append(value)
ans = knapsack(w, W, V)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# AtCoder DP Task D - Knapsack 1
def knapsack(target, W, V): # target=knapsack weight
    P = [[0] * (target + 1) for _ in range(len(V))]
    for vi in range(len(V)):
        for w in range(target + 1):
            if vi > 0:
                P[vi][w] = P[vi - 1][w] # same value without vi-th item
                if w >= W[vi]:
                    new = P[vi - 1][w - W[vi]] + V[vi]
                    if new > P[vi][w]: # most value
                        P[vi][w] = new
            else:
                if w >= W[vi]:
                    P[vi][w] = V[vi]
    return P[len(V) - 1][target]

assert knapsack(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

n, w = map(int, input().split())
W, V = [], []
for _ in range(n):
    weight, value = map(int, input().split())
    W.append(weight)
    V.append(value)
ans = knapsack(w, W, V)
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(1, n+1):
    for w in range(W+1):
        weight, value = obj[i-1]
        DP[i][w] = max(DP[i-1][w], DP[i][w])
        if w + weight <= W:
            DP[i][w + weight] = max(DP[i - 1][w] + value, DP[i][w + weight])

ans = max(DP[n])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W = map(int,input().split())
WV = np.zeros((N,2))
for i in range(N):
    w,v = map(int,input().split())
    WV[i,0] = w
    WV[i,1] = v
dp = np.zeros((N+1,W+1))

for i in range(N):
    for j in range(W+1):
        if j >= WV[i,0]:
            weight = j-WV[i,0]
            dp[i+1,j] = np.maximum(dp[i,j],dp[i,int(weight)]+WV[i,1])
        else:
            dp[i+1,j] = np.maximum(dp[i,j],dp[i+1,j])

print(int(dp[N,W]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
N, W = map(int, input().split())
def knapsack():
  dp = np.zeros((N+1, W+1), dtype=int)
  c = np.arange(1, N+1)
  cc = np.arange(1, W+1)
  for i in c:
    w, v = map(int, input().split())
    for sum_w in cc:
      if sum_w - w >= 0:
        dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-w] + v)
      dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])
  return dp[-1][-1]
print(knapsack())

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
wvlist = list([list(map(int,input().split())) for _ in range(N)])
dp = [[0 for _ in range(W+1)] for __ in range(N+1)]
for i in range(1,N+1):
    for w in range(1,W+1):
        #i番目の荷物が選べる場合
        if w-wvlist[i-1][0] >= 0:
            #debug用
            #print('i:',i,'w:',w)
            
            #「i-1番目のdp値」と「i番目を用いた値」を比較
            dp[i][w] = max(dp[i-1][w-wvlist[i-1][0]]+wvlist[i-1][1],dp[i-1][w])
            
        #i番目の荷物を選ばない場合
        else:
            dp[i][w] = dp[i-1][w]
#debug用
#print(dp)
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
N, W = map(int, input().split())
def knapsack():
  dp = np.zeros((N+1, W+1), dtype=int)
  for i in range(1, N+1):
    w, v = map(int, input().split())
    for sum_w in range(1, W+1):
      if sum_w - w >= 0:
        dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-w] + v)
      dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])
  return dp[-1][-1]
print(knapsack())

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
N, W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)
for i in range(N):
  w[i], v[i] = map(int, input().split())
def knapsack(w, v):
  dp = np.zeros((N+1, W+1), dtype=int)
  for i in range(1, N+1):
    for sum_w in range(1, W+1):
      if sum_w - w[i-1] >= 0:
        dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-w[i-1]] + v[i-1])
      dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])
  return dp[-1][-1]
print(knapsack(w, v))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
N, W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)
for i in range(N):
  w[i], v[i] = map(int, input().split())
dp = np.zeros((N+1, W+1), dtype=int)
for i in range(1, N+1):
  for sum_w in range(1, W+1):
    if sum_w - w[i-1] >= 0:
      dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-w[i-1]] + v[i-1])
    dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
N, W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)
for i in range(N):
  w[i], v[i] = map(int, input().split())
dp = np.zeros((N+1, W+1), dtype=int)
for i in range(1, N+1):
  for sum_w in range(1, W+1):
    if sum_w - w[i-1] >= 0:
      dp[i][sum_w] = max([dp[i-1][sum_w], dp[i-1][sum_w-w[i-1]] + v[i-1], dp[i][sum_w]])
    else:
      dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W = map(int,input().split())
WV = np.zeros((N,2))
for i in range(N):
    w,v = map(int,input().split())
    WV[i,0] = w
    WV[i,1] = v
dp = np.zeros((N+1,W+1))

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

print(int(dp[N,W]))

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
WV = [[0,0] for i in range(N)]
for i in range(N):
    w,v = map(int,input().split())
    WV[i][0] = w
    WV[i][1] = v
dp = [[0 for i in range(W+1)]for j in range(N+1)]

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
wt = [0] * (n)
vl = [0] * (n)
for x in range(n):
    wt[x], vl[x] = map(int, input().split())

dp = [[0 for y in range(w + 1)] for x in range(n + 1)]

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

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int, input().split())
wt = []
vl = []
for x in range(n):
    wv = [int(i) for i in input().split()]
    wt.append(wv[0])
    vl.append(wv[1])

dp = [[0 for y in range(w+1)] for x in range(n+1)]

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

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
def kp(n, w, val, wt):
    if n==1:
        if wt[0]<=w:
            return val[0]
        return 0
    
    dp = [dp[:]for dp in[[0]*(w+1)]*(n+1)]
    # print(dp)
    for i in range(n+1):
        for j in range(w+1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif wt[i-1] <= j:
                dp[i][j] = max(dp[i-1][j], val[i-1]+dp[i-1][j-wt[i-1]])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][w]


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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# dpD - Knapsack 1 (01 knapsack problem)
import sys
input = sys.stdin.readline

def knapsack(W: int, weight: "Array[int]", value: "Array[int]") -> int:
    # dp[i] := optimum value of Weight i
    dp = [0] * (W + 1)
    for w, v in zip(weight, value):
        for cur_w in range(W, w - 1, -1):
            dp[cur_w] = max(dp[cur_w], dp[cur_w - w] + v)
    return dp[-1]


def main():
    N, W = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    weight, value = zip(*A)
    ans = knapsack(W, weight, value)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
w = []
v = []
for _ in range(N):
    x, y = map(int,input().split())
    w.append(x)
    v.append(y)
    
dp = [ [0 for i in range(W+1)] for j in range(N+1) ]

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
# dp[i][w_sum]: i-1番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

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

dp = [[0 for w_sum in range(W+100)] for i in range(N+100)]

for i in range(N):
    for w_sum in range(W+1):

        # i-1番目の品物を選ぶ場合
        # 重量的に入れられるなら入れてみる
        if w_sum-items[i][0] >= 0:
            dp[i+1][w_sum] = max(dp[i+1][w_sum],
                                 dp[i][w_sum-items[i][0]]+items[i][1])

        # i-1番目の品物を選ばない場合
        dp[i+1][w_sum] = max(dp[i+1][w_sum], dp[i][w_sum])

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
n,W=map(int,raw_input().split())
w=[]
val=[]
for i in range(n):
    p=map(int,raw_input().split())
    w.append(p[0])
    val.append(p[1])
dp = [0]*(W+1)
for i in range(n):
    for j in range(W,w[i]-1,-1):
        dp[j]=max(dp[j],dp[j-w[i]]+val[i])
print dp[-1]

Submission status: Time Limit Exceeded

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

dp = [0]*(w+1)

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

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, w = list(map(int, input().split()))
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
dp = np.zeros((n + 1,w + 1))
for i in range(n):
    for j in range(w+1):
        if data[i][0] > j:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - data[i][0]] + data[i][1])
print(int(dp[n - 1][w]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

INF = 10 ** 10

N, W = map(int, sys.stdin.readline().rstrip().split(" "))
wvs = []
for _ in range(N):
    w, v = map(int, sys.stdin.readline().rstrip().split(" "))
    wvs.append((w, v))


memo = [[0 for _ in range(W+1)] for _1 in range(N)]

def solve():
    for n in range(N):
        current_w, current_v = wvs[n]
        for w in range(W+1):
            if n == 0:
                if w - current_w >= 0:
                    memo[n][w] = current_v
                else:
                    memo[n][w] = 0
            else:
                if w-current_w >= 0:
                    memo[n][w] = max(memo[n-1][w], memo[n-1][w-current_w] + current_v)
                else:
                    memo[n][w] = memo[n - 1][w]
        # print(memo)
    return memo[-1][-1]


ans = solve()
print(ans)
exit(0)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

INF = 10 ** 10

N, W = map(int, sys.stdin.readline().rstrip().split(" "))
wvs = []
for _ in range(N):
    w, v = map(int, sys.stdin.readline().rstrip().split(" "))
    wvs.append((w, v))


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

def max_value(n_index, w):
    current_w, current_v = wvs[n_index]
    if w < 0:
        return -INF
    if n_index == -1:
        # print(n_index, w, 0)
        return 0
    else:
        if memo[n_index][w] > 0:
            return memo[n_index][w]
        # print(n_index, w, "->", n_index-1, w, "|", n_index, w-current_w)
        res = max(max_value(n_index - 1, w), max_value(n_index-1, w - current_w) + current_v)
        # print(n_index, w, res)
        memo[n_index][w] = res
        return res


ans = max_value(N-1, W)
print(ans)
exit(0)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

INF = 10 ** 10

N, W = map(int, sys.stdin.readline().rstrip().split(" "))
wvs = []
for _ in range(N):
    w, v = map(int, sys.stdin.readline().rstrip().split(" "))
    wvs.append((w, v))


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

def max_value(n_index, w):
    current_w, current_v = wvs[n_index]
    if w < 0:
        return -INF
    if n_index == -1:
        # print(n_index, w, 0)
        return 0
    else:
        if memo[n_index][w] > 0:
            return memo[n_index][w]
        # print(n_index, w, "->", n_index-1, w, "|", n_index, w-current_w)
        res = max(max_value(n_index - 1, w), max_value(n_index-1, w - current_w) + current_v)
        # print(n_index, w, res)
        return res


ans = max_value(N-1, W)
print(ans)
exit(0)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

INF = 10 ** 10

N, W = map(int, sys.stdin.readline().rstrip().split(" "))
wvs = []
for _ in range(N):
    w, v = map(int, sys.stdin.readline().rstrip().split(" "))
    wvs.append((w, v))


def max_value(n_index, w):
    current_w, current_v = wvs[n_index]
    if w < 0:
        return -INF
    if n_index == -1:
        # print(n_index, w, 0)
        return 0
    else:
        # print(n_index, w, "->", n_index-1, w, "|", n_index, w-current_w)
        res = max(max_value(n_index - 1, w), max_value(n_index-1, w - current_w) + current_v)
        # print(n_index, w, res)
        return res


ans = max_value(N-1, W)
print(ans)
exit(0)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
import numpy as np
dp = np.zeros((n+1, w+1), np.int64)
for i in list(range(n+1))[1:]:
    wi, vi = map(int, input().split())
    dp[i] = [max(dp[i-1][j], dp[i-1][j-wi]+vi) if j >= wi else dp[i-1][j] for j in range(w+1)]
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
import numpy as np
dp = np.zeros((n+1, w+1))
for i in list(range(n+1))[1:]:
    wi, vi = map(int, input().split())
    dp[i] = [max(dp[i-1][j], dp[i-1][j-wi]+vi) if j >= wi else dp[i-1][j] for j in range(w+1)]
print(int(max(dp[-1])))

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
import numpy as np
dp = np.zeros((n+1, w+1))
for i in list(range(n+1))[1:]:
    wi, vi = map(int, input().split())
    for j in range(w+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi]+vi) if j >= wi else dp[i-1][j]
print(int(max(dp[-1])))

Submission status: Time Limit Exceeded

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


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0]*(W+1) for _ in range(N+2)]
    #dp = [0]*(W+1)
    for i in range(N):
        for sum_w in range(W):
            if sum_w+w[i] <=W:
                dp[i+1][sum_w+w[i]] = max(dp[i][sum_w+w[i]], dp[i][sum_w]+v[i])
                #dp[sum_w+w[i]] = max(dp[sum_w+w[i]], dp[sum_w]+v[i])
            #dp[i+1][sum_w] = dp[i][sum_w]
            dp
        dp[i+2] = dp[i+1].copy()
    return max(dp[-1])


# Generated by 1.1.4 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))
    print(solve(N, W, w, v))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

nin = np.fromstring(sys.stdin.buffer.read(), dtype=np.int64, sep=' ')
N = nin[0]
W = nin[1]
wv = nin[2: 2 * N + 2].reshape(N, 2).T
w = wv[0]
v = wv[1]
dp = np.zeros((N + 1, W + 1), dtype=np.int64)
for i in range(N):
    for j in range(w[i]):
        dp[i + 1, j] = dp[i, j]
    for j in range(w[i],  W + 1):
        dp[i + 1, j] = max(dp[i, j], dp[i, j - w[i]] + v[i])
print(dp[N, W])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
Mod = 1000000007



def main(): #startline-------------------------------------------
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for i in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    dp = [[0]*(W+1) for i in range(N+1)]
    for i in range(W):
        dp[N][i] = 0
    for i in range(N-1,-1,-1):
        for j in range(W+1):
            if j < w[i]:
                dp[i][j] = dp[i+1][j]
            else:
                dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
    print(dp[0][W])
if __name__ == "__main__":
    main() #endline===============================================




def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n < 2 is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))):
        if prime[i] == 1:
            for j in range(2*i,n):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n):
        if prime[i] == 1:
            res.append(i)
    return res

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

Submission status: Time Limit Exceeded

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

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

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

print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
import os, sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")
 
sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10**18
MOD = 10**9 + 7

def N(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))
def bulk_li(): return list(map(lambda s: list(map(int, s.split())), sys.stdin.readlines()))

n, w = li()
wv = bulk_li()

# print(wv)
table = dict()

# 以下の条件で最大の価値の総和を返す
# i番目以降(i+1..n)の品物 / 残重量jのナップサック
def dp(i, j):
    if i == n:
        return 0
    if (i, j) in table:
        return table.get((i, j))

    w, v = wv[i]
    if w > j:
        return dp(i+1, j)

    table[(i, j)] = max(v + dp(i+1, j-w), dp(i+1, j))
    return table[(i, j)]

print(dp(0, w))


"""
TLE
https://atcoder.jp/contests/dp/submissions/6675353

recursionでやると遅い。
"""

Submission status: Time Limit Exceeded

Solution code:
import os, sys
import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")
 
sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10**18
MOD = 10**9 + 7

def N(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))
def bulk_li(): return list(map(lambda s: list(map(int, s.split())), sys.stdin.readlines()))

n, w = li()
wv = bulk_li()

# print(wv)
table = dict()

# 以下の条件で最大の価値の総和を返す
# i番目以降(i+1..n)の品物 / 残重量jのナップサック
def dp(i, j):
    if i == n:
        return 0
    if (i, j) in table:
        return table.get((i, j))

    w, v = wv[i]
    if w > j:
        return dp(i+1, j)

    table[(i, j)] = max(v + dp(i+1, j-w), dp(i+1, j))
    return table[(i, j)]

print(dp(0, w))

Submission status: Time Limit Exceeded

Solution code:
# dpD - Knapsack 1
# 貰うDP
import sys
input = sys.stdin.readline

def main():
    n, w = tuple(map(int, input().rstrip().split()))
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(n))
    dp = [0] * (w + 1)
    for i in range(n):
        for j in range(w, A[i][0] - 1, -1):
            dp[j] = max(dp[j], dp[j - A[i][0]] + A[i][1])
    print(max(dp))
    


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n, w = [int(e) for e in input().split()]
  d = [[int(e) for e in input().split()] for i in range(n)]
  t = {}
  t[w] = 0
  for i in range(n):
    keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
    tw, tv = d[i]
    for j in keys:
      nw = j - tw
      if nw < 0:
        continue
      nv = t[j] + tv
      if nw in t:
        if nv > t[nw]:
          t[nw] = nv
      else:
        t[nw] = nv
  print(max(t.values()))
main()

Submission status: Time Limit Exceeded

Solution code:
n, w = [int(e) for e in input().split()]
t = [-1 for i in range(w + 1)]
t[w] = 0
for _ in range(n):
  nw, nv = [int(e) for e in input().split()]
  for i in range(nw, w + 1):
    if t[i] == -1:
      continue
    if t[i - nw] < t[i] + nv:
      t[i - nw] = t[i] + nv
print(max(t))