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:
from functools import cmp_to_key

def main():
  n, w = [int(e) for e in input().split()]
  d = [[int(e) for e in input().split()] for i in range(n)]
  d.sort(key = cmp_to_key(lambda x, y: y[1] / y[0] - x[1] / x[0]))
  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]:
          for k in list(t.keys()):
            if k < nw and t[k] <= nv:
              del t[k]
          t[nw] = nv
      else:
        Flag = False
        for k in t:
          if nw < k and nv <= t[k]:
            Flag = True
            break
        if Flag:
          continue
        for k in list(t.keys()):
          if k < nw and t[k] <= nv:
            del t[k]
        t[nw] = nv
  print(max(t.values()))

main()

Submission status: Time Limit Exceeded

Solution code:
from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: y[1] / y[0] - x[1] / x[0]))
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]:
        for k in list(t.keys()):
          if k < nw and t[k] <= nv:
            del t[k]
        t[nw] = nv
    else:
      Flag = False
      for k in t:
        if nw < k and nv <= t[k]:
          Flag = True
          break
      if Flag:
        continue
      for k in list(t.keys()):
        if k < nw and t[k] <= nv:
          del t[k]
      t[nw] = nv
        
print(max(t.values()))

Submission status: Time Limit Exceeded

Solution code:
from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: y[1] / y[0] - x[1] / x[0]))
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]:
        for k in list(t.keys()):
          if k <= nw and t[k] <= nv:
            del t[k]
        t[nw] = nv
    else:
      Flag = False
      for k in t:
        if nw <= k and nv <= t[k]:
          Flag = True
          break
      if Flag:
        continue
      for k in list(t.keys()):
        if k <= nw and t[k] <= nv:
          del t[k]
      t[nw] = nv
        
print(max(t.values()))

Submission status: Time Limit Exceeded

Solution code:
from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: y[1] / y[0] - x[1] / x[0]))
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  updates = []
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw not in t or nv > t[nw]:
      for u in updates:
        if nw <= u[0] and nv <= u[1]:
          continue
      updates.append([nw, nv])
  for key in list(t.keys()):
    for u in updates:
        if key <= u[0] and t[key] <= u[1]:
          del t[key]
          break
  for u in updates:
    t[u[0]] = u[1]
print(max(t.values()))

Submission status: Time Limit Exceeded

Solution code:
from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: y[1] / y[0] - x[1] / x[0]))
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  updates = []
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw not in t or nv > t[nw]:
      for u in updates:
        if nw <= u[0] and nv <= u[1]:
          continue
      updates.append([nw, nv])
  for u in updates:
    t[u[0]] = u[1]
print(max(t.values()))

Submission status: Time Limit Exceeded

Solution code:
from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: x[1] / x[0] - y[1] / y[0]))
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()))

Submission status: Time Limit Exceeded

Solution code:
from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: y[1] / y[0] - x[1] / x[0]))
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]:
        for k in list(t.keys()):
          if k <= nw and t[k] < nv:
            del t[k]
        t[nw] = nv
    else:
      Flag = False
      for k in t:
        if nw <= k and nv <= t[k]:
          Flag = True
          break
      if Flag:
        continue
      for k in list(t.keys()):
        if k <= nw and t[k] < nv:
          del t[k]
      t[nw] = nv
        
print(max(t.values()))

Submission status: Time Limit Exceeded

Solution code:
from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: x[1] / x[0] - y[1] / y[0]))
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]:
        for k in list(t.keys()):
          if k <= nw and t[k] < nv:
            del t[k]
        t[nw] = nv
    else:
      Flag = False
      for k in t:
        if nw <= k and nv <= t[k]:
          Flag = True
          break
      if Flag:
        continue
      for k in list(t.keys()):
        if k <= nw and t[k] < nv:
          del t[k]
      t[nw] = nv
        
print(max(t.values()))

Submission status: Time Limit Exceeded

Solution code:
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]:
        for k in list(t.keys()):
          if k <= nw and t[k] < nv:
            del t[k]
        t[nw] = nv
    else:
      Flag = False
      for k in t:
        if nw <= k and nv <= t[k]:
          Flag = True
          break
      if Flag:
        continue
      for k in list(t.keys()):
        if k <= nw and t[k] < nv:
          del t[k]
      t[nw] = nv
        
print(max(t.values()))

Submission status: Time Limit Exceeded

Solution code:
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]:
        for k in list(t.keys()):
          if k <= nw and t[k] < nv:
            del t[k]
        t[nw] = nv
    else:
      Flag = False
      for k in t:
        if nw <= k and nv <= t[k]:
          Flag = True
          break
      if Flag:
        continue
      for k in list(t.keys()):
        if k <= nw and t[k] < nv:
          del t[k]
      t[nw] = nv
        
print(max(t.values()))

Submission status: Time Limit Exceeded

Solution code:
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]
  updates = []
  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
        updates.append([nw, nv])
    else:
      t[nw] = nv
      updates.append([nw, nv])
  for u in updates:
    for key in list(t.keys()):
      if u[0] > key and u[1] >= t[key]:
        del t[key]
print(max(t.values()))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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()))

Submission status: Time Limit Exceeded

Solution code:
cache = {}

def memoize(f):
  global cache
  def _(*args):
    if not args in cache:
      cache[args] = f(*args)
    return cache[args]
  return _

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

@memoize
def f(i, w, v):
  if i == n:
    return v
  if d[i][0] <= w:
    return max(f(i + 1, w - d[i][0], v + d[i][1]), f(i + 1, w, v))
  else:
    return f(i + 1, w, v)  
print(f(0, w, 0))

Submission status: Time Limit Exceeded

Solution code:
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]

def f(i, w, v):
  if i == n:
    return v
  if d[i][0] <= w:
    return max(f(i + 1, w - d[i][0], v + d[i][1]), f(i + 1, w, v))
  else:
    return f(i + 1, w, v)  
print(f(0, w, 0))

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

for i, (w, v) in enumerate(WV):
    for j in range(W+1):
        if w <= j:
            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: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
Weight = []
Value = []
for i in range(N):
    tmp_w,tmp_v = map(int,input().split())
    Weight.append(tmp_w)
    Value.append(tmp_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-Weight[i]>=0:
            dp[i+1][j] = max(dp[i][j],dp[i][j-Weight[i]]+Value[i])
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j])
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
Weight = []
Value = []
for i in range(N):
    tmp_w,tmp_v = map(int,input().split())
    Weight.append(tmp_w)
    Value.append(tmp_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-Weight[i]>=0:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j-Weight[i]]+Value[i])
        else:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
ans = 0
for i in range(N+1):
    ans = max(ans,max(dp[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    max_weight, list_of_weight_and_value = read()
    result = think(max_weight, list_of_weight_and_value)
    write(result)


def read():
    n, max_weight = read_int(2)
    list_of_weight_and_value = []
    for i in range(n):
        list_of_weight_and_value.append(read_int(2))
    return max_weight, list_of_weight_and_value


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(max_weight, list_of_weight_and_value):
    MAX_WEIGHT = 10 ** 5
    MAX_N = 100
    INVALID_VALUE = MAX_WEIGHT * MAX_N + 1

    # dp[w] means max value at total weight 'w'
    dp = [INVALID_VALUE for x in range(max_weight + len(list_of_weight_and_value) + 1)]
    dp[0] = 0

    for weight, value in list_of_weight_and_value:
        for i in range(len(dp) - 1, -1, -1):
            if dp[i] != INVALID_VALUE and i + weight < len(dp):
                if dp[i + weight] == INVALID_VALUE:
                    dp[i + weight] = dp[i] + value
                else:
                    dp[i + weight] = max(dp[i + weight], dp[i] + value)
    return max(filter(lambda x: x != INVALID_VALUE, dp[:max_weight + 1]))


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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


def main():
    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 j in range(W+1):
        dp[0][j] = 0

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

    print(dp[N][W])


if __name__ == "__main__":
    main()

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 ww,vv in wv_list:
    for i in range(w, ww-1, -1):
        t = dp[i-ww] + vv
        if dp[i] < t:
            dp[i] = t
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 ww,vv in wv_list:
    for i in range(w, ww-1, -1):
        t = dp[i-ww] + vv
        dp[i] = max(dp[i], t)
print(max(dp))

Submission status: Time Limit Exceeded

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

weight = []

N, W = map(int, input().split())
for i in range(N):
    array = list(map(int, input().split()))
    weight.append(array)

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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


for i in range(n):
    wi, vi = map(int, input().split())
    sum_w = 0
    while sum_w <= w:
        if sum_w - wi >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - wi] + vi)
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
        sum_w += 1

print(dp[n][w])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    n, W = readi(2)
    ws, vs = zip(*readi(n, 2))
    dp = arr(n + 1, W + 1)
    for i in range(n):
        for w in range(W + 1):
            if w - ws[i] >= 0:
                dp[i + 1][w] = max(dp[i + 1][w], dp[i][w - ws[i]] + vs[i])
            dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
    print(dp[n][W])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

dp = [[0 for i in range(2*W)] for j in range(2*N)]

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
from copy import *
from sys import *
from math import *
import queue
from collections import defaultdict,Counter,deque

setrecursionlimit(1000000)

#dp[i][w]
def main():
	n,w = map(int,input().split())
	wv = [list(map(int,input().split())) for i in range(n)]
	dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
	for i in range(1,n+1):
		cw = wv[i-1][0]
		cv = wv[i-1][1]
		for j in range(w+1):
			dp[i][j] = max(dp[i-1][j],dp[i-1][j-cw] + cv) if j-cw >= 0 else dp[i-1][j]
	print(dp[-1][-1])

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	#競プロ用のQueue
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)

class Stack():
	#怯プロ用のStack
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

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

value = [[-1 for j in range(W + 1)] for i in range(N + 1)]

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

ans = max(value[N])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

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

value = [[-1 for j in range(W + 1)] for i in range(N + 1)]

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

ans = max(max(value))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

value = [[-1 for j in range(W + 1)] for i in range(N + 1)]

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

ans = max(max(value))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
import numpy as np
N,W = map(int, sys.stdin.readline().split())

items= [ list(map(int, sys.stdin.readline().split()) )for _ in range(N)]


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

#dp[今何個目か][重さ何キロ持つか] = その時の価値の最大値
dp[0][0] = 0

for i in range(W+1): #重さ i のときに得られる価値
    for j in range(N):  # j 個目の荷物で
        w,v = items[j]
        if i >= w: # w > i だと前提が破綻するので
            #遷移 d[j + 1][i] =  (d[j][i - w] + v ) 新しい荷物を選んだ場合
            dp[j + 1 ][i] = dp[j][i - w]  + v  # dp[j][i - w]  + v → j 個持ったところに、更に 価値v のitemが追加されて j+ 1になった
        dp[j + 1][i] =  max(dp[j + 1][i] ,dp[j][i]) #選ばなかった場合

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

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
N,W = map(int, sys.stdin.readline().split())

items= [ list(map(int, sys.stdin.readline().split()) )for _ in range(N)]


dp = [[0 for _ in range(W+1)] for _ in range(N + 1) ]
#dp[今何個目か][重さ何キロ持つか] = その時の価値の最大値
dp[0][0] = 0

for i in range(W+1): #重さ i のときに得られる価値
    for j in range(N):  # j 個目の荷物で
        w,v = items[j]
        if i >= w: # w > i だと前提が破綻するので
            #遷移 d[j + 1][i] =  (d[j][i - w] + v ) 新しい荷物を選んだ場合
            dp[j + 1 ][i] = dp[j][i - w]  + v  # dp[j][i - w]  + v → j 個持ったところに、更に 価値v のitemが追加されて j+ 1になった
        dp[j + 1][i] =  max(dp[j + 1][i] ,dp[j][i]) #選ばなかった場合

print(dp[N][W])

Submission status: Time Limit Exceeded

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

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


dp = [[0 for _ in range(W+1)] for _ in range(N + 1) ]
#dp[今何個目か][重さ何キロ持つか] = その時の価値の最大値
dp[0][0] = 0




for i in range(W+1): #重さ i のときに得られる価値
    for j in range(N):  # j 個目の荷物で
        w,v = items[j]
        if i >= w: # w > i だと前提が破綻するので
            #遷移 d[j + 1][i] =  (d[j][i - w] + v ) 新しい荷物を選んだ場合
            dp[j + 1 ][i] = dp[j][i - w]  + v  # dp[j][i - w]  + v → j 個持ったところに、更に 価値v のitemが追加されて j+ 1になった
        dp[j + 1][i] =  max(dp[j + 1][i] ,dp[j][i]) #選ばなかった場合

print(dp[N][W])

Submission status: Time Limit Exceeded

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

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


dp = [[0 for _ in range(W+1)] for _ in range(N + 1) ]
#dp[今何個目か][重さ何キロ持つか] = その時の価値の最大値
dp[0][0] = 0
for j in range(N): #j 個目の荷物で
    for i in range(W+1): #重さ i のときに得られる価値
        w,v = items[j]
        if i >= w: # w > i だと前提が破綻するので
            #遷移 d[j + 1][i] =  (d[j][i - w] + v ) 新しい荷物を選んだ場合
            dp[j + 1 ][i] = dp[j][i - w]  + v  # dp[j][i - w]  + v → j 個持ったところに、更に 価値v のitemが追加されて j+ 1になった
        dp[j + 1][i] =  max(dp[j + 1][i] ,dp[j][i]) #選ばなかった場合
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, raw_input().split())
l  = []
for n in xrange(N):
    l.append(map(int, raw_input().split()))

dp = [0]*(W+1)

for i in xrange(0, N):
    noww = l[i][0]
    nowv = l[i][1]
    for w in xrange(W, 0, -1):
        if w>0 and w+noww<=W: dp[w+noww] = max(dp[w+noww], dp[w]+nowv)

    dp[noww] = nowv

print max(dp)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def solve():
  a,b=map(int,input().split())
  c=[list(map(int,input().split())) for i in range(a)]
  d=[[0 for i in range(b+1)]for j in range(a)]
  for i in range(b-c[0][0]+1):
    d[0][c[0][0]+i]=c[0][1]
  
  for i in range(1,a):
    for j in range(0,b+1):
      if j<c[i][0]:
        d[i][j]=d[i-1][j]
      else:
        d[i][j]=max(d[i-1][j],d[i-1][j-c[i][0]]+c[i][1])
  print(d[-1][-1])
                    
solve()

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a)]
d=[[0 for i in range(b+1)]for j in range(a)]
for i in range(b-c[0][0]+1):
  d[0][c[0][0]+i]=c[0][1]
  
for i in range(1,a):
  for j in range(0,b+1):
    if j<c[i][0]:
      d[i][j]=d[i-1][j]
    else:
      d[i][j]=max(d[i-1][j],d[i-1][j-c[i][0]]+c[i][1])
print(d[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
val=[]
we=[]
for i in range(n):
  a,b=map(int,input().split())
  we.append(a)
  val.append(b)
dp=[[0 for _ in range(w+1)]for _ in range(n+1)]
for i in range(n+1):
  for j in range(w+1):
    if i==0 or j==0:
      continue
    if we[i-1]>j:
      dp[i][j]=dp[i-1][j]
    else:
      dp[i][j]=max(dp[i-1][j],val[i-1]+dp[i-1][j-we[i-1]])
print(dp[n][w])

Submission status: Time Limit Exceeded

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def solve(N, W, WVs):
    dp = [[0 for _ in range(W + 1)] for __ in range(N + 1)]
    # dp[i][w] => i 番目まででWを超えない範囲での最大価値
    for i in range(N + 1):
        for w in range(W + 1):
            weight, value = WVs[i - 1]
            if w - weight >= 0:
                dp[i][w] = max(dp[i - 1][w],
                               dp[i - 1][w - weight] + value)
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[N][W]


if __name__ == "__main__":
    N, W = tuple(map(int, input().split(" ")))
    WVs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, W, WVs))