Problem:


Score : 400 points

Problem Statement

You have N items and a bag of strength W.
The i-th item has a weight of w_i and a value of v_i.

You will select some of the items and put them in the bag.
Here, the total weight of the selected items needs to be at most W.

Your objective is to maximize the total value of the selected items.

Constraints

1 ≤ N ≤ 100

1 ≤ W ≤ 10^9

1 ≤ w_i ≤ 10^9

For each i = 2,3,...,N, w_1 ≤ w_i ≤ w_1 + 3.

1 ≤ v_i ≤ 10^7

W, each w_i and v_i are integers.

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 total value of the selected items.

Sample Input 1

4 6
2 1
3 4
4 10
3 4

Sample Output 1

11

The first and third items should be selected.

Sample Input 2

4 6
2 1
3 7
4 10
3 6

Sample Output 2

13

The second and fourth items should be selected.

Sample Input 3

4 10
1 100
1 100
1 100
1 100

Sample Output 3

400

You can take everything.

Sample Input 4

4 1
10 100
10 100
10 100
10 100

Sample Output 4

0

You can take nothing.



Sample input:
4 6
2 1
3 4
4 10
3 4


Sample output:
11

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, W = getNM()
query = [getList() for i in range(N)]
wei = []
val = []
for i in range(N):
    w, v = query[i]
    wei.append(w)
    val.append(v)

wei_min = min(wei)
wei_max = max(wei)

def knapsack_1(N, limit, weight, value):
    dp = [[0] * (limit + 1) for i in range(N + 1)]
    dp[0][0] = 0

    for i in range(N):
        # wei_minごと飛ばす
        for k in range(0, limit, wei_min):
            for j in range(0 + k, min(500 + k, limit + 1, (wei_max * (i + 1)) + 1)):
                if weight[i] <= j:
                    dp[i + 1][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])
                else:
                    dp[i + 1][j] = dp[i][j]
    return max(dp[N])

print(knapsack_1(N, W, wei, val))

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, W = getNM()
query = [getList() for i in range(N)]
wei = []
val = []
for i in range(N):
    w, v = query[i]
    wei.append(w)
    val.append(v)

wei_min = min(wei)

def knapsack_1(N, limit, weight, value):
    dp = [[0] * (limit + 1) for i in range(N + 1)]
    dp[0][0] = 0

    for i in range(N):
        # wei_minごと飛ばす
        for k in range(0, limit + 1, wei_min):
            for j in range(0 + k, min(500 + k, limit + 1)):
                if weight[i] <= j:
                    dp[i + 1][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])
                else:
                    dp[i + 1][j] = dp[i][j]
    return dp[N][limit]

print(knapsack_1(N, W, wei, val))

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
w = []
v = []
for i in range(n):
  w_, v_ = map(int, input().split())
  w.append(w_)
  v.append(v_)

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

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

Submission status: Runtime Error

Solution code:
def main():
    n, w, *wv = map(int, open(0).read().split())
    dp = [[0] * (w + 1) for _ in range(n + 1)]

    *q, = zip(*[iter(wv)] * 2)

    for i in range(1, n + 1):
        a, b = q[i - 1]
        if a > w:
            continue

        tmp = dp[i - 1][a]

        dp[i - 1][a] = max(dp[i - 1][a], b)

        dp[i][:a + 1] = dp[i - 1][:a + 1]

        for j in range(w + 1 - a):
            if dp[i - 1][j]:
                dp[i][j + a] = max(dp[i - 1][j + a], dp[i - 1][j] + b)

        if tmp == 0:
            for k in range(2 * a, w + 1, a):
                dp[i][k] = 0

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, w, *wv = map(int, open(0).read().split())
    dp = [0] * (w + 1)

    for a, b in zip(*[iter(wv)] * 2):
        if a > w:
            continue

        tmp = dp[a]
        dp[a] = max(dp[a], b)
        dp = dp[:a] + [max(dp[i + a], dp[i] + b) if dp[i] else dp[i + a] for i in range(w + 1 - a)]
        if tmp == 0:
            for i in range(2 * a, w + 1, a):
                dp[i] = 0

    ans = max(dp)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
n,W=map(int,input().split())
wv=[list(map(int,input().split()))]
w0=wv[0][0]-1
wv[0][0]=1
# すべてのwからw0を引く
for _ in range(n-1):
  w,v=list(map(int,input().split()))
  wv.append([w-w0,v])
import numpy as np
dp=np.full((n+1,401),0,int)
# dp[k][w]:k個で重さwでの最大価値
dp[0]=0
for w,v in wv:
  for i in range(n):
    dp[n-i][w:]=np.maximum(dp[n-i][w:],dp[n-i-1][:-w]+v)
ans=0
for i in range(1,n+1):
  if W-i*w0<=0:break
  ans=max(ans,dp[i][W-i*w0])
print(ans)

Submission status: Runtime Error

Solution code:
n,W=map(int,input().split())
wv=[list(map(int,input().split()))]
w0=wv[0][0]-1
wv[0][0]=1
# すべてのwからw0を引く
for _ in range(n-1):
  w,v=list(map(int,input().split()))
  wv.append([w-w0,v])
import numpy as np
dp=np.full((n+1,301),0,int)
# dp[k][w]:k個で重さwでの最大価値
dp[0]=0
for w,v in wv:
  for i in range(n):
    dp[n-i][w:]=np.maximum(dp[n-i][w:],dp[n-i-1][:-w]+v)
ans=0
for i in range(1,n+1):
  if W-i*w0<=0:break
  ans=max(ans,dp[i][W-i*w0])
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

N, W = map(int, input().split())
weight = []
value = []

for _ in range(N):
  w, v = map(int, input().split())
  value.append(v)
  weight.append(w)
  
def solveDP(N, W, value, weight):
    dp = np.zeros((N+1, W+1))
    
    for i in range(N):
        for w in range(W+1):
            if w >= weight[i]:
                dp[i + 1, w] = max(dp[i, w - weight[i]] + value[i], dp[i, w])
            else:
                dp[i + 1, w] = dp[i, w]
    
    return dp[N , W ]

print(int(solveDP(N, W, value, weight)))

Submission status: Runtime Error

Solution code:
def main():
    N, W = map(int, input().split())
    l = []
    w, v = map(int, input().split())
    ww = w
    dp = [[[0] * (3*N) for _ in range(N+1) ]for _ in range(N)]
    dp[0][1][0] = v
    l.append((0, v))
    for _ in range(N-1):
        w, v = map(int, input().split())
        l.append((w-ww, v))
    if W < ww:
        return 0
    for i in range(1, N):
        w, v = l[i]
        for j in range(1, N+1):
            for k in range(w):
                dp[i][j][k] = dp[i-1][j][k]
            for k in range(w, 3*N):
                dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k-w] + v)
    r = 0
    for i in range(N+1):
        wt = W - i * ww
        r = max(r, max(dp[-1][i][:wt+1]))
    return r
print(main())

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    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())
    if w[0]>3*N:
        w0=w[0]
        W=max(W//w0*3*N+W%w0,(3*N+3)*N)
        for i in range(N):
            w[i]-=w0
            w[i]+=3*N
    dp=[[0]*(W+1) for _ in range(N+1)]
    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]>=0:
                dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
    print(dp[-1][-1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    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())
    if w[0]>3*N:
        w0=w[0]
        W=W//w0*3*N+W%w0
        for i in range(N):
            w[i]-=w0
            w[i]+=3*N
    dp=[[0]*(W+1) for _ in range(N+1)]
    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]>=0:
                dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
    print(dp[-1][-1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    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())
    if w[0]>=4*N:
        w0=w[0]
        W=W//w0*4*N+W%w0
        for i in range(N):
            w[i]-=w0*(i+1)
            w[i]+=4*N*i
    dp=[[0]*(W+1) for _ in range(N+1)]
    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]>=0:
                dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
    print(dp[-1][-1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

n,w = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp=[[ 0 for i in range(w+1)] for j in range(n+1)]

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

for i in range(1,N+1):
  w,v=map(int,input().split())
  for j in range(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)
print(max(dp[-1]))

Submission status: Runtime Error

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

wv.sort(key=lambda x:(x[0],-x[1]))
#print(wv)
#exit()
#wv.sort()
min_v = wv[0][0]
cnt = 0
num = [0]*4

for i in range(n):
    num[wv[i][0] - wv[0][0]] +=1
        
#dp = [[[0 for i in range(n)] for j in range(n)] for k in range(n)]

#print(wv)

t_num3 = []
tmp = 0
for i in range(num[3]):
    tmp += wv[n-num[3]-1+i][1]
    t_num3.append(tmp)

t_ans = 0
t_num0 = 0
ans = 0

for i in range(num[0]+1):
    if i != 0:
        t_num0 += wv[i-1][1]
    #print(t_ans,i)
    t_num1 = 0
    for j in range(num[1]+1):
        if j != 0:
            t_num1 += wv[num[0]+j-1][1]
        t_num2 = 0
        for k in range(num[2]+1):
            if k != 0:
                t_num2 += wv[num[0]+num[1]+k-1][1]
            ima_w = min_v*(i+j+k) + 1*j+2*k
            idx = (w - ima_w)//(min_v+3) - 1
            if ima_w > w:
                continue
            elif num[3] == 0 or idx < 0:
                t_ans = t_num0+t_num1+t_num2
            else:
                t_ans = t_num0+t_num1+t_num2 + t_num3[min(idx,num[3])]
        #print(t_ans)
        ans = max(t_ans,ans)

print(ans)

Submission status: Runtime Error

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

wv.sort(key=lambda x:(x[0],-x[1]))
#print(wv)
#exit()
#wv.sort()
min_v = wv[0][0]
cnt = 0
num = [0]*4

for i in range(n):
    num[wv[i][0] - wv[0][0]] +=1
        
dp = [[[0 for i in range(n)] for j in range(n)] for k in range(n)]

#print(wv)

t_num3 = []
tmp = 0
for i in range(num[3]):
    tmp += wv[n-num[3]-1+i][1]
    t_num3.append(tmp)

t_ans = 0
t_num0 = 0
ans = 0

for i in range(num[0]+1):
    if i != 0:
        t_num0 += wv[i-1][1]
    #print(t_ans,i)
    t_num1 = 0
    for j in range(num[1]+1):
        if j != 0:
            t_num1 += wv[num[0]+j-1][1]
        t_num2 = 0
        for k in range(num[2]+1):
            if k != 0:
                t_num2 += wv[num[0]+num[1]+k-1][1]
            ima_w = min_v*(i+j+k) + 1*j+2*k
            if ima_w > w:
                continue
            elif num[3] == 0:
                t_ans = t_num0+t_num1+t_num2
            else:
                t_ans = t_num0+t_num1+t_num2 + t_num3[min((w - ima_w)//(min_v+3),num[3])]
        #print(t_ans)
        ans = max(t_ans,ans)

print(ans)

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
dd = defaultdict(list)
for i in range(n):
    weight, value = map(int, input().split())
    dd[weight].append(value)

for k in dd.keys():
    dd[k].sort(reverse=True)

a = min(dd.keys())
b, c, d = a+1, a+2, a+3
ans = 0
for w in range(len(dd[a])+1):
    for x in range(len(dd[b])+1):
        for y in range(len(dd[c])+1):
            for z in range(len(dd[d])+1):
                if W < a*w+b*x+c*y+d*z:
                    break
                val = sum(dd[a][:w])+sum(dd[b][:x]) + \
                    sum(dd[c][:y])+sum(dd[d][:z])
                ans = max(ans, val)
print(ans)

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
weights, values = zip(*[tuple(map(int, input().split()))for _ in range(n)])
min_w = min(weights)-1
weights = [weight-min_w for weight in weights]
W_MAX = 4*200
dp = [[0]*(W_MAX+1) for _ in range(n+1)]
for i in range(1, n+1):
    for k in reversed(range(1, n+1)):
        for j in range(1, W_MAX+1):
            if j-weights[i-1] < 0:
                continue
            dp[k][j] = max(dp[k][j], dp[k-1][j-weights[i-1]]+values[i-1])

ans = 0
for k in range(n+1):
    w_max = w-k*min_w
    if w_max < 0 <= W_MAX:
        continue
    ans = max(ans, dp[k][w_max])
print(ans)

Submission status: Runtime Error

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

N,W = map(int,input().split())
w = []
v = []
for _ in range(N):
    w_, v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

# dp[i][j]:iまでを用いて、重みjの時の最大値
dp = [[0]*(W+1) for _ in range(N+1)]

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

Submission status: Runtime Error

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

# dp[i][j]:iまでを用いて、重みjの時の最大値
dp = [[0]*(W+1) for _ in range(N+1)]

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
n,w = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(n)]
#dp[i][j]はi番目まででj(価値の合計)になる重さの最小値
sum_value = 0
for i in range(n):
  sum_value += wv[i][1]
dp = [[float("inf")]*(sum_value+1) for j in range(n)]
for k in range(sum_value+1):
  if k == wv[0][1]:
    dp[0][k] = wv[0][0]
for a in range(n-1):
  for b in range(sum_value+1):
    if dp[a][b-wv[a+1][1]] != float("inf"):
      dp[a+1][b] = min(dp[a][b-wv[a+1][1]]+wv[a+1][0],dp[a][b])
    elif b == wv[a+1][1]:
      dp[a+1][b] = min(wv[a+1][0],dp[a][b])
    else:
      dp[a+1][b] = dp[a][b]
ans = 0
for c in range(sum_value+1):
  if dp[-1][c] != float("inf") and w >= dp[-1][c]:
    ans = c
print(ans)

Submission status: Runtime Error

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

dp = [[[-1] * (3 * n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 0
w1 = wv[0][0]

for i, (w, v) in enumerate(wv):
    for j in range(i + 1):
        for k in range(3 * n + 1):
            if dp[i][j][k] != -1:
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
                w_diff = w - w1
                if j + 1 <= n and k + w_diff <= 3 * n:
                    dp[i+1][j+1][k+w_diff] = max(dp[i+1][j+1][k+w_diff], dp[i][j][k] + v)

ans = 0
for j in range(n + 1):
    w_diff_mx = W - w1 * j
    for k in range(w_diff_mx + 1):
        ans = max(ans, dp[n][j][k])

print(ans)

Submission status: Runtime Error

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

import bisect

def main():
    mod=10**9+7
    N,W=MI()
    w=[0]*N
    v=[0]*N
    for i in range(N):
        w[i],v[i]=MI()
    w1=w[0]
    for i in range(N):
        w[i]-=w1
        
    a=set([])
    for i in range(N+1):
        for j in range(3*i+1):
            ww=w1*i+j
            if ww>W:
                break
            a.add(ww)
    a=list(a)
    M=len(a)
    
    
    #dp[i][j]はiまでの商品で,重さa[j]のときの価値の最大
    dp=[[-1]*(M) for _ in range(N+1)]
    dp[0][0]=0
    ans=0
    
    for i in range(N):
        for j in range(M):
            if dp[i][j]!=-1:
                dp[i+1][j]=max(dp[i+1][j],dp[i][j])
                ww=a[j]+w1+w[i]
                if ww<=W:
                    jj=bisect.bisect_left(a,ww)
                    dp[i+1][jj]=max(dp[i+1][jj],dp[i][j]+v[i])

    print(max(dp[-1]))
    
     
    
            

main()

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N, W = read_values()
    I = [tuple(read_values()) for _ in range(N)]

    w0 = I[0][0]
    if w0 > W:
        print(0)
        return

    dp = [
        [[0 for _ in range(N * 3 + 100)] for __ in range(N + 10)]
        for ___ in range(N + 10)
    ]

    for i, (w1, v) in enumerate(I):
        w = w1 - w0
        for k in range(N):
            for j in range(N * 3 + 5):
                dp[i + 1][k][j] = max(dp[i][k][j], dp[i + 1][k][j])
                if j + w > N * 3 + 10:
                    continue
                dp[i + 1][k + 1][j + w] = max(dp[i][k][j] + v, dp[i + 1][k + 1][j + w])

    res = 0
    for k in range(N + 1):
        r = W - k * w0
        if r < 0:
            continue
        for i in range(W - k * w0 + 1):
            res = max(res, dp[N][k][i])
    print(res)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N, W = read_values()
    I = [tuple(read_values()) for _ in range(N)]

    w0 = I[0][0]
    if w0 > W:
        print(0)
        return

    dp = [
        [[0 for _ in range(N * 3 + 100)] for __ in range(N + 10)]
        for ___ in range(N + 10)
    ]

    for i, (w1, v) in enumerate(I):
        w = w1 - w0
        for k in range(N):
            for j in range(N * 3 + 5):
                dp[i + 1][k][j] = max(dp[i][k][j], dp[i + 1][k][j])
                dp[i + 1][k + 1][j + w] = max(dp[i][k][j] + v, dp[i + 1][k + 1][j + w])

    res = 0
    for k in range(N + 1):
        r = W - k * w0
        if r < 0:
            continue
        for i in range(W - k * w0 + 1):
            res = max(res, dp[N][k][i])
    print(res)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N, W = read_values()
    I = [tuple(read_values()) for _ in range(N)]

    w0 = I[0][0]
    if w0 > W:
        print(0)
        return

    dp = [
        [[0 for _ in range(N * 3 + 100)] for __ in range(N + 10)]
        for ___ in range(N + 10)
    ]

    for i, (w1, v) in enumerate(I):
        w = w1 - w0
        for k in range(N):
            for j in range(N * 3 + 5):
                dp[i + 1][k][j] = max(dp[i][k][j], dp[i + 1][k][j])
                dp[i + 1][k + 1][j + w] = max(dp[i][k][j] + v, dp[i + 1][k + 1][j + w])

    res = 0
    for vdp in dp:
        for k in range(N + 1):
            for i in range(W - k * w0 + 1):
                res = max(res, vdp[k][i])
    print(res)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N, W = read_values()
    I = [tuple(read_values()) for _ in range(N)]

    w0 = I[0][0]
    if w0 > W:
        print(0)
        return

    dp = [
        [[0 for _ in range(N * 3 + 10)] for __ in range(N + 10)] for ___ in range(N + 10)
    ]

    for i, (w1, v) in enumerate(I):
        w = w1 - w0
        for k in range(N):
            for j in range(N * 3 + 5):
                dp[i + 1][k][j] = max(dp[i][k][j], dp[i + 1][k][j])
                dp[i + 1][k + 1][j + w] = max(dp[i][k][j] + v, dp[i + 1][k + 1][j + w])

    res = 0
    for vdp in dp:
        for k in range(N + 1):
            for i in range(W - k * w0 + 1):
                res = max(res, vdp[k][i])
    print(res)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N, W = read_values()
    I = [tuple(read_values()) for _ in range(N)]

    w0 = I[0][0]
    if w0 > W:
        print(0)
        return

    dp = [
        [[0 for _ in range(N * 3 + 10)] for __ in range(N + 1)] for ___ in range(N + 1)
    ]

    for i, (w1, v) in enumerate(I):
        w = w1 - w0
        for k in range(N):
            for j in range(N * 3 + 5):
                dp[i + 1][k][j] = max(dp[i][k][j], dp[i + 1][k][j])
                dp[i + 1][k + 1][j + w] = max(dp[i][k][j] + v, dp[i + 1][k + 1][j + w])

    res = 0
    for vdp in dp:
        for k in range(N + 1):
            for i in range(W - k * w0 + 1):
                res = max(res, vdp[k][i])
    print(res)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N,W=map(int, input().split())
dp = np.zeros(W+1, dtype=np.int)
for i in range(N):
  wi,vi=map(int,input().split())
  dp[wi:]=np.maximum(dp[wi:], dp[:-wi]+vi)
print(dp[W])

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
wv=[]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    wv.append([a,b])
    v.append(b)
v.sort(reverse=True)
ans=0
w0=wv[0][0]
for i in range(1,n+1):
    wp=w-w0*i
    if wp<0:
        continue
    elif wp>=3*i:
        ans=max(ans,sum(v[:i]))
    else:
        dp=[-1 for iii in range(wp+1)]
        dp[0]=0
        for j in range(n):
            for k in range(wp,-1,-1):
                if dp[k]>=0 and k+wv[i][0]-w0<=wp:
                    dp[k+wv[i][0]-w0]=max(dp[k]+wv[i][1],dp[k+wv[i][0]-w0])
        ans=max(max(dp),ans)
print(ans)

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
wv=[]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    wv.append([a,b])
    v.append(b)
v.sort(reverse=True)
ans=0
w0=wv[0][0]
for i in range(1,n+1):
    wp=w-w0*i
    if wp<0:
        continue
    elif wp>=3*i:
        ans=max(ans,sum(v[:i]))
    else:
        dp=[-1 for iii in range(wp+1)]
        dp[0]=0
        for j in range(n):
            for k in range(wp,-1,-1):
                if dp[k]>=0:
                    dp[k+wv[i][0]-w0]=max(dp[k]+wv[i][1],dp[k+wv[i][0]-w0])
        ans=max(max(dp),ans)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(3000)
N,W = map(int,input().split())
wv = []
for _ in range(N):
  w,v = map(int,input().split())
  wv.append([w,v])
memo = [[0]*(W+1) for i in range(N+1)]
def rec(n,uplimit_w):
  if memo[n][uplimit_w] > 0:
    return memo[n][uplimit_w]
  ans = 0
  if n == N:
    return 0
  elif wv[n][0] > uplimit_w:
    return rec(n+1,uplimit_w)
  else:
    ans = max(rec(n+1,uplimit_w),rec(n+1,uplimit_w - wv[n][0])+wv[n][1])
    memo[n][uplimit_w] = ans
    return memo[n][uplimit_w]
print(rec(0,W))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(3000)
N,W = map(int,input().split())
wv = []
for _ in range(N):
  w,v = map(int,input().split())
  wv.append([w,v])
memo = [[0]*(W+1) for i in range(N+1)]
def rec(n,uplimit_w):
  if memo[n][uplimit_w] > 0:
    return memo[n][uplimit_w]
  ans = 0
  if n == N:
    return 0
  elif wv[n][0] > uplimit_w:
    return rec(n+1,uplimit_w)
  else:
    ans = max(rec(n+1,uplimit_w),rec(n+1,uplimit_w - wv[n][0])+wv[n][1])
    memo[n][uplimit_w] = ans
    return ans
print(rec(0,W))

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
wv = []
for _ in range(N):
  w,v = map(int,input().split())
  wv.append([w,v])
memo = [[0]*(W+1) for i in range(N+1)]
def rec(n,uplimit_w):
  if memo[n][uplimit_w] > 0:
    return memo[n][uplimit_w]
  ans = 0
  if n == N:
    return 0
  elif wv[n][0] > uplimit_w:
    return rec(n+1,uplimit_w)
  else:
    ans = max(rec(n+1,uplimit_w),rec(n+1,uplimit_w - wv[n][0])+wv[n][1])
    memo[n][uplimit_w] = ans
    return ans
print(rec(0,W))

Submission status: Runtime Error

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

#i:N,j:W,value:value
dp = [[0]*(W+1) for i in range(N+1)]

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

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