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:
def larger(x, y):
	if x > y: return x
	return y

N, W = map(int, input().split())
weightlist = []
valuelist = []
for i in range(0, N):
	inpt = list(map(int, input().split()))
	weightlist.append(inpt[0])
	valuelist.append(inpt[1])
dp = []
for i in range(0, N+1):
	lst = []
	for j in range(0, W+1):
		lst.append(0)
	dp.append(lst)
memo = [0]
for i in range(0, N):
	memolength = len(memo)
	for j in range(0, memolength):
		now = memo.pop(0)
		memo.append(now)
		dp[i+1][now] = larger(dp[i][now], dp[i+1][now])
		if now+weightlist[i] <= W:
			if now+weightlist[i] not in memo: memo.append(now+weightlist[i])
			dp[i+1][now+weightlist[i]] = larger(dp[i][now]+valuelist[i], dp[i][now+weightlist[i]])
max = 0
for i in range(0, W+1):
	max = larger(max, dp[N][i])
print(max)

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 for _ in range(W+1)] for _ in range(N+1)]

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:

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

value = []
weight = []

for i in range(0,N):
	a,b = input().split(' ')
	weight.append(int(a))
	value.append(int(b))

dp = []
for i in range(0,N+1):
	temp = [-1]*(W+1)
	dp.append(temp)

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N,W  = raw_input().split(' ')
N = int(N)
W = int(W)

value = []
weight = []

for i in range(0,N):
	a,b = raw_input().split(' ')
	weight.append(int(a))
	value.append(int(b))

dp = []
for i in range(0,N+1):
	temp = [-1]*(W+1)
	dp.append(temp)

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
def sub():
    N, W = [int(e) for e in input().split()]
    ww = []
    vv = []
    for _ in range(N):
        w, v = [int(e) for e in input().split()]
        ww.append(w)
        vv.append(v)
    
    # dp_table = [[0]*(W+1)]*(N+1)
    dp_table = [[0 for _ in range(W+1)] for _ in range(N+1)]
    # print(len(dp_table), len(dp_table[0]))
    for i in range(N):
        for j in range(W):
            w_next = j+ww[i]
            v_next = vv[i]
            if w_next <= W:
                dp_table[i+1][w_next] = max(dp_table[i+1][w_next], dp_table[i][j] + v_next)
            dp_table[i+1][j] = max(dp_table[i+1][j], dp_table[i][j])


    print(max(dp_table[-1]))
    # print(max(dp_table))

sub()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
def sub():
    N, W = [int(e) for e in input().split()]
    ww = []
    vv = []
    for _ in range(N):
        w, v = [int(e) for e in input().split()]
        ww.append(w)
        vv.append(v)
     
    @lru_cache(maxsize=None) 
    def dp(a_index, a_cum):
        if a_index == N:
            return 0
        w_next = a_cum+ww[a_index]
        if w_next <= W:
            a = dp(a_index+1, a_cum+ww[a_index]) + vv[a_index]
            b = dp(a_index+1, a_cum)
            return max(a,b)
        else:
            return dp(a_index+1, a_cum)

    print(dp(0, 0))

sub()

Submission status: Time Limit Exceeded

Solution code:
def task(N, W, weight, value, result_dict):
    if (N == 0) or (W == 0):
        result_dict[(N, W)] = 0
        return 0
    
    if (N-1, W) in result_dict:
        a = result_dict[(N-1, W)]
    else:
        a = task(N-1, W, weight, value, result_dict)
            
    if weight[N - 1] <= W:
        if (N-1, W - weight[N - 1]) in result_dict:
            b = result_dict[(N-1, W - weight[N - 1])] + value[N-1]
        else:
            b = task(N - 1, W - weight[N - 1], weight, value, result_dict) + value[N - 1]
        result_dict[(N, W)] = max(a, b)
    else:
        result_dict[(N, W)] = a
    
    return result_dict[(N, W)]

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

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

Submission status: Time Limit Exceeded

Solution code:
def task(N, W, weight, value, result_dict):
    if (N == 0) or (W == 0):
        result_dict[(N, W)] = 0
        return 0
    if (N, W) in result_dict:
        return result_dict[(N, W)]
    if weight[N - 1] <= W:
        a = task(N-1, W, weight, value, result_dict)
        b = task(N - 1, W - weight[N - 1], weight, value, result_dict) + value[N - 1]
        result_dict[(N, W)] = max(a, b)
    else:
        result_dict[(N, W)] = task(N-1, W, weight, value, result_dict)
    
    return result_dict[(N, W)]

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

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

Submission status: Time Limit Exceeded

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

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 = [[-1] *(W + 1) for i in range(N + 1)]
    
def dfs(i, W):
    if dp[i][W] != -1:
        return dp[i][W]
    if i == N:
        ans = 0
    elif w[i] > W:
        ans = dfs(i + 1, W)
    else:
        ans = max(dfs(i + 1, W), dfs(i + 1, W - w[i]) + v[i])
    dp[i][W] = ans
    return ans

print(dfs(0, W))

Submission status: Time Limit Exceeded

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


def solve(N: int, M: int, W: "List[int]", V: "List[int]"):
    dp = [[0 for i in range(M+1)] for j in range(N+1)]

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

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



    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = list(map(int, input().split()))
dp = np.zeros((N, W+1), dtype=int)
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)

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

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

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

Submission status: Time Limit Exceeded

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

weight = [0]*110
value = [0]*110
dp = [[0]*100010 for i in range(110)]

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

# dp roop
for i in range(N):
  sum_w = 0
  while sum_w <= W:
    if sum_w >= weight[i]:
      dp[i+1][sum_w] = max(dp[i][sum_w - weight[i]] + value[i], dp[i][sum_w])
    else:
      dp[i+1][sum_w] = dp[i][sum_w]
    sum_w += 1
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

def chmax(a, b):
  if a<b:
    a = b
  return a

weight = np.array([0]*110)
value = np.array([0]*110)
dp = np.array([[0]*100010 for i in range(110)])

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

# dp roop
for i in range(N):
  sum_w = 0
  while sum_w <= W:
    if (sum_w - weight[i]) >= 0:
      dp[i+1][sum_w] = chmax(dp[i+1][sum_w],
                             dp[i][sum_w - weight[i]] + value[i])
    dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w])
    sum_w += 1
print(dp[N][W])

Submission status: Time Limit Exceeded

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

def chmax(a, b):
  if a<b:
    a = b
  return a

weight = [0]*110
value = [0]*110
dp = [[0]*100010 for i in range(110)]
    
N, W = map(int, input().split())
for i in range(N):
  weight[i], value[i] = map(int, input().split())

# dp roop
for i in range(N):
  sum_w = 0
  while sum_w <= W:
    if (sum_w - weight[i]) >= 0:
      dp[i+1][sum_w] = chmax(dp[i+1][sum_w],
                             dp[i][sum_w - weight[i]] + value[i])
    dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w])
    sum_w += 1
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, os
 
def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]
 
    wi, vi = inp[2], inp[3]
 
 
    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi
    
    def calcer(dp,m,wi,vi):
        for j in range(m, wi-1, -1):
            if dp[j] < vi + dp[j - wi]:
                dp[j] = vi + dp[j - wi]
        
    for i in range(n - 1):
        calcer(dp, m, inp[2*i + 4], inp[2*i + 5])
 
    print(dp[-1])
main()

Submission status: Time Limit Exceeded

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


def main():
    n, m = map(int, input().split())
    wi, vi = map(int, input().split())

    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi, vi = map(int, input().split())
        for j in reversed(range(m + 1 - wi)):
            if dp[j + wi] < vi + dp[j]:
                dp[j + wi] = vi + dp[j]

    print(dp[-1])


main()

Submission status: Time Limit Exceeded

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


def main():
    inp = os.read(0, os.fstat(0).st_size).split()
    n = int(inp[0])
    m = int(inp[1])

    wi = int(inp[2])
    vi = int(inp[3])

    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = int(inp[2 * i + 4])
        vi = int(inp[2 * i + 5])
        for j in reversed(range(m + 1 - wi)):
            if dp[j + wi] < vi + dp[j]:
                dp[j + wi] = vi + dp[j]

    print(dp[-1])


main()

Submission status: Time Limit Exceeded

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

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    wi, vi = inp[2], inp[3]


    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in range(m, wi-1, -1):
            if dp[j] < vi + dp[j - wi]:
                dp[j] = vi + dp[j - wi]

    print(dp[-1])
main()

Submission status: Time Limit Exceeded

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


def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n = inp[0]
    m = inp[1]

    wi = inp[2]
    vi = inp[3]

    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2 * i + 4]
        vi = inp[2 * i + 5]
        for j in reversed(range(m + 1 - wi)):
            if dp[j + wi] < vi + dp[j]:
                dp[j + wi] = vi + dp[j]

    print(dp[-1])


main()

Submission status: Time Limit Exceeded

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


def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n = inp[0]
    m = inp[1]

    wi = inp[2]
    vi = inp[3]

    dp = [0] * (m + 1)
    for j in range(m + 1 - wi):
        dp[j + wi] = vi

    for i in range(n - 1):
        wi = inp[2 * i + 4]
        vi = inp[2 * i + 5]
        for j in reversed(range(m + 1 - wi)):
            if dp[j + wi] < vi + dp[j]:
                dp[j + wi] = vi + dp[j]

    print(dp[-1])


main()

Submission status: Time Limit Exceeded

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

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    wi, vi = inp[2], inp[3]


    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        j = m
        while j >= wi:
            if dp[j] < vi + dp[j - wi]:
                dp[j] = vi + dp[j - wi]
            j -= 1

    print(dp[-1])
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import io
import os


def main():
    buffer = map(int, os.read(0, os.fstat(0).st_size).split())
    n, m = next(buffer), next(buffer)
    dp = [0] * (m + 1)
    wi, vi = next(buffer), next(buffer)
    for i in range(wi, m + 1):
        dp[i] = vi

    for i in range(n - 1):
        wi, vi = next(buffer), next(buffer)
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])


main()

Submission status: Time Limit Exceeded

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

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    wi, vi = inp[2], inp[3]


    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in reversed(range(wi, m + 1)):
            if dp[j] < vi + dp[j - wi]:
                dp[j] = vi + dp[j - wi]

    print(dp[-1])
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import io
import os


def main():
    buffer = list(map(int, os.read(0, os.fstat(0).st_size).split()))
    m = buffer[1]
    dp = [0] * (m + 1)
    v1 = buffer[3]
    for i in range(buffer[2], m + 1):
        dp[i] = v1

    for i in range(buffer[0] - 1):
        wi, vi = buffer[4 + 2 * i], buffer[5 + 2 * i]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, w = map(int, input().split())
    dp = [0] * (w + 1)
    for i in range(n):
        x, y = map(int, input().split())
        
        for j in range(w, x - 1, -1):
            dp[j] = max(dp[j], dp[j - x] + y)
    
    print(max(dp))
    return 0

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import io
import os


def main():
    buffer = list(map(int, os.read(0, os.fstat(0).st_size).split()))
    m = buffer[1]
    dp = [0] * (m + 1)
    v1 = buffer[3]
    for i in range(buffer[2], m + 1):
        dp[i] = v1

    for i in range(buffer[0] - 1):
        wi, vi = buffer[4 + 2 * i], buffer[5 + 2 * i]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])


input = io.BytesIO().readline
main()

Submission status: Time Limit Exceeded

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

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    wi, vi = inp[2], inp[3]


    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import io
import os


def main():
    n, m = map(int, input().split())
    wi, vi = map(int, input().split())

    dp = [0] * (m + 1)
    for i in range(wi, m + 1):
        dp[i] = vi

    for i in range(n - 1):
        wi, vi = map(int, input().split())
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()

Submission status: Time Limit Exceeded

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

def main():
    inp = [int(x) for x in sys.stdin.buffer.read().split()]
    n, m = inp[0],inp[1]

    w, v = inp[2::2], inp[3::2]

    dp = [0] * (m + 1)
    for j in range(w[0], m + 1):
        dp[j] = v[0]

    for i in range(n - 1):
        vi = v[i + 1]
        wi = w[i + 1]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])
main()

Submission status: Time Limit Exceeded

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

def main():
    input = sys.stdin.buffer.readline
    n, m = 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] * (m + 1)
    for j in range(w[0], m + 1):
        dp[j] = v[0]

    for i in range(n - 1):
        vi = v[i + 1]
        wi = w[i + 1]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import io
import os


def main():
    n, m = 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] * (m + 1)
    for i in range(w[0], m + 1):
        dp[i] = v[0]
    for i in range(n - 1):
        for j in reversed(range(w[i + 1], m + 1)):
            dp[j] = max(v[i + 1] + dp[j - w[i + 1]], dp[j])

    print(dp[-1])


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import io
import os


def main():
    n, m = 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] * (m + 1)
    for i in range(w[0], m + 1):
        dp[i] = v[0]
    for i in range(n - 1):
        dp = [dp[j] if j < w[i + 1] else max(v[i + 1] + dp[j - w[i + 1]], dp[j]) for j in range(m + 1)]

    print(dp[-1])


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    n, m = 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] * (m + 1)
    for j in range(w[0], m + 1):
        dp[j] = v[0]

    for i in range(n - 1):
        vi = v[i+1]
        wi = w[i + 1]
        for j in reversed(range(w[i + 1],m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
n, m = 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] * (m + 1)
for j in range(w[0], m + 1):
    dp[j] = v[0]

for i in range(n - 1):
    vi = v[i + 1]
    wi = w[i + 1]
    for j in reversed(range(w[i + 1], m + 1)):
        dp[j] = max(vi + dp[j - wi], dp[j])

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import io
import os


def main():
    n, m = 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] * (m + 1)
    for j in range(w[0], m + 1):
        dp[j] = v[0]

    for i in range(n - 1):
        next_dp = [0] * (m + 1)
        for j in range(m + 1):
            if j < w[i + 1]:
                next_dp[j] = dp[j]
            else:
                next_dp[j] = max(v[i + 1] + dp[j - w[i + 1]], dp[j])
        dp = next_dp

    print(dp[-1])


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    n, m = 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] * (m + 1)
    for j in range(w[0], m + 1):
        dp[j] = v[0]

    for i in range(n - 1):
        next_dp = [0] * (m + 1)
        for j in range(m + 1):
            if j < w[i + 1]:
                next_dp[j] = dp[j]
            else:
                next_dp[j] = max(v[i + 1] + dp[j - w[i + 1]], dp[j])
        dp = next_dp

    print(dp[-1])


main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
n, m = 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] * (m + 1)
for j in range(w[0], m + 1):
    dp[j] = v[0]

for i in range(n - 1):
    next_dp = [0] * (m + 1)
    for j in range(m + 1):
        if j < w[i + 1]:
            next_dp[j] = dp[j]
        else:
            next_dp[j] = max(v[i + 1] + dp[j - w[i + 1]], dp[j])
    dp = next_dp

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
n, m = 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] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

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

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

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
l1=[]
for i in range(0,n):
    wt,v=map(int,input().split())
    l1.append((wt,v))
l1.sort()
ans=[ [0]*(w+1) for _ in range(n+1) ]
for i in range(0,n+1):
    for j in range(0,w+1):
        
        if (i==0 or j==0) :
            ans[i][j]=0
        else :
            if l1[i-1][0]<=j:
                ans[i][j]=max(l1[i-1][1]+ans[i-1][j-l1[i-1][0]],ans[i-1][j])
            else :
                ans[i][j]=ans[i-1][j]

print(ans[n][w])

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
l1=[]
for i in range(0,n):
    wt,v=map(int,input().split())
    l1.append((wt,v))
l1.sort()
ans=[ [0]*w for _ in range(n) ]
def solve(n,w):
    if w==0 or n==0:
        return 0
    elif ans[n-1][w-1]!=0:
        return ans[n-1][w-1]
    elif l1[n-1][0]>w:
        return solve(n-1,w)
        
    else :
        ans[n-1][w-1]=max (l1[n-1][1]+solve(n-1,w-l1[n-1][0]),solve(n-1,w))
        return ans[n-1][w-1]

solve(n,w)
print(ans[n-1][w-1])

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
l1=[]
for i in range(0,n):
    wt,v=map(int,input().split())
    l1.append((wt,v))
l1.sort()
ans=[0]*n
def solve(n,w):
    if w==0 or n==0:
        return 0
    elif l1[n-1][0]>w:
        return solve(n-1,w)
    else :
        ans[n-1]=max (l1[n-1][1]+solve(n-1,w-l1[n-1][0]),solve(n-1,w))
        return ans[n-1]
solve(n,w)
print(ans[n-1])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
"""
問題
https://atcoder.jp/contests/dp/tasks/dp_d

解説
https://qiita.com/drken/items/dc53c683d6de8aeacf5a#d-%E5%95%8F%E9%A1%8C---knapsack-1
"""

def solve():
    N, LIMIT = list(map(int, input().split()))
    W, V = [None], [None]
    for i in range(N):
        w, v = list(map(int, input().split()))
        W.append(w)
        V.append(v)
    
    # dp[i][w] := i個目までの品物を選んだ時の、重さがwのときの価値の最大値
    dp = [[w for w in range(LIMIT+1)] for i in range(N+1)]
    for w in range(LIMIT+1):
        dp[0][w] = 0
    
    #O(N*LIMIT) = O(10**7)
    for i in range(1, N+1):
        for w in range(LIMIT+1):
            if w-W[i] >= 0:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i]] + V[i])
            else:
                dp[i][w] = dp[i-1][w]

    ans = 0
    for w in range(LIMIT+1):
        ans = max(ans, dp[N][w])

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

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

items = []
for _ in range(N):
  items.append(list(map(int,input().split())))

def f(dp,wleft,index):
  if index > N:
    return 0
  if dp[wleft][index] is not None:
    return dp[wleft][index]
  
  if wleft < items[index-1][0]:
    return f(dp,wleft,index+1)
  dp[wleft][index] = max(f(dp,wleft,index+1),items[index-1][1]+f(dp,wleft-items[index-1][0],index+1))
  return dp[wleft][index]
  
print(f(dp,W,1))

Submission status: Time Limit Exceeded

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

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

items = []
for _ in range(N):
  items.append(list(map(int,input().split())))

def f(dp,wleft,index):
  if index > N:
    return 0
  if dp[wleft][index] is not None:
    return dp[wleft][index]
  
  if wleft < items[index-1][0]:
    return f(dp,wleft,index+1)
  
  return max(f(dp,wleft,index+1),items[index-1][1]+f(dp,wleft-items[index-1][0],index+1))
  
print(f(dp,W,1))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,W=map(int,input().split())
wei=[]
val=[]
for _ in range(n):
    x,y=map(int,input().split())
    wei.append(x)
    val.append(y)
dp=[[0 for p in range(W+1)] for q in range(n+1)]
for i in range(n):
    for w in range(W+1):
        if wei[i]<=w:
            dp[i+1][w]=max(dp[i][w-wei[i]]+val[i],dp[i][w])
        else:
            dp[i+1][w]=dp[i][w]
print(dp[n][W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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 w > sum_w:
			dp[i, sum_w] = dp[i-1, sum_w]
		else:
			dp[i, sum_w] = max(dp[i-1, sum_w], dp[i-1, sum_w - w] + v)
		#print(sum_w, dp)

print(dp.max())

Submission status: Time Limit Exceeded

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

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


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

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

Submission status: Time Limit Exceeded

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


def main():
    print(search_with_memo(0, W))


def search_with_memo(i, rest):
    if memo[i][rest] != None:
        return memo[i][rest]

    if i == N:
        return 0
    elif rest < items[i].w:
        through = search_with_memo(i + 1, rest)
        memo[i+1][rest] = through
        return through
    else:
        selected = search_with_memo(i+1, rest - items[i].w) + items[i].v
        memo[i+1][rest - items[i].w] = selected
        through = search_with_memo(i+1, rest)
        memo[i+1][rest] = through
        return max(selected, through)


def all_search(i, rest):
    if i == N:
        return 0
    elif rest < items[i].w:
        return all_search(i+1, rest)
    else:
        selected = all_search(i+1, rest - items[i].w) + items[i].v
        through = all_search(i+1, rest)
        return max(selected, through)


class Item():

    def __init__(self, v, w):
        self.v = v
        self.w = w


if __name__ == "__main__":
    N, W = [int(ele) for ele in input().split()]
    items = [None] * N
    memo = [[None] * (W*2) for _ in range(N*2)]
    for idx in range(N):
        w, v = [int(ele) for ele in input().split()]
        items[idx] = Item(v, w)

    main()

Submission status: Time Limit Exceeded

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

def f(n,W):
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i, (w, v) in enumerate(wv):
        dp[i + 1][:w] = dp[i][:w]
        for j, (v1, v2) in enumerate(zip(dp[i], dp[i][w:])):
            nv = v1 + v
            if nv > v2:
                dp[i + 1][j + w] = nv
            else:
                dp[i + 1][j + w] = v2
    print(dp[-1][-1])

n, W = map(int, input().split())
f(n,W)

Submission status: Time Limit Exceeded

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

def f(n,W):
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [0] + [-1] * W
    dp[0] = 0
    for w, v in wv:
        ndp = deepcopy(dp)
        for i, (dpi, dpj) in enumerate(zip(dp, dp[w:])):
            if dpi == -1: continue
            nv = dpi + v
            if nv > dpj:
                ndp[i + w] = nv
        dp = ndp
    print(max(dp))

n, W = map(int, input().split())
f(n,W)

Submission status: Time Limit Exceeded

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

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 w,v in wv:
    for i in range(W,w-1,-1):
        nv=dp[i-w]+v
        if nv>dp[i]:
            dp[i]=nv
print(dp[-1])