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: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,W = inpl() 
a = [inpl() for _ in range(n)]
a.sort(key = lambda x:x[1], reverse = True)
a.sort(key = lambda x:x[0])
b = [[0] for _ in range(4)]
f = a[0][0]
ind = 0
for i in range(n):
    w,v = a[i]
    if w != f:
        ind += 1
        f = w
    b[ind].append(b[ind][-1] + v)
f = a[0][0]
v,x,y,z = [len(x) for x in b]
# print(b)
li = itertools.product(range(v),range(x),range(y),range(z))
res = 0
for tmp in li:
    # print(tmp)
    ww = sum(tmp[i]*(f+i) for i in range(4))
    vv = sum(b[i][tmp[i]] for i in range(4))
    # print(ww,vv)
    if ww <= W:
        res = max(res, vv)
print(res)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

n, w = map(int, readline().split())
wv = [tuple(map(int, readline().split())) for i in range(n)]
dp = defaultdict(int)
dp[0] = 0

for ww, v in wv:
    for xw, xv in list(dp.items()):
        if ww + xw <= w:
            dp[ww + xw] = max(dp[ww + xw], v + xv)
print(max(dp.values()))

Submission status: Accepted

Solution code:
def main():
    n, w_lim = map(int, input().split())
    group = {}
    min_w = 0
    for i in range(n):
        w, v = map(int, input().split())
        if i == 0:
            group = {x: [] for x in range(w, w + 4)}
            min_w = w
        group[w].append(v)
    length = [len(group[i]) + 1 for i in range(min_w, min_w + 4)]
    for i in range(min_w, min_w + 4):
        group[i].sort(reverse=True)
        for j in range(1, length[i - min_w] - 1):
            group[i][j] += group[i][j - 1]
        group[i] = [0] + group[i]
    answer = 0
    for i in range(length[0]):
        for j in range(length[1]):
            for k in range(length[2]):
                for l in range(length[3]):
                    if w_lim < min_w * i + (min_w + 1) * j + (min_w + 2) * k + (min_w + 3) * l:
                        break
                    answer = max(answer, group[min_w][i] + group[min_w + 1][j] + group[min_w + 2][k] + group[min_w + 3][l])
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,W = inpl() 
a = [inpl() for _ in range(n)]
a.sort(key = lambda x:x[1], reverse = True)
a.sort()
b = []
now = a[0][0]
li = []
for i in range(n):
    w,v = a[i]
    if now == w:
        li.append(v)
    else:
        now = w
        b.append(li)
        li = []
        li.append(v)
if li != []: b.append(li)
kind = now - a[0][0] + 1
f = a[0][0]
for i in range(len(b)):
    b[i] = b[i][::-1]

c = [[0] for _ in range(4)]
for i,l in enumerate(b):
    for x in l:
        c[i].append(c[i][-1] + x)
    c[i] = c[i]
# print(c)
ln = [len(x) for x in c]
res = 0
def chk(w,v):
    global res
    if w <= W:
        res = max(res, v)
x,y,z,w = ln
# print(ln)
for i in range(x):
    for j in range(y):
        for k in range(z):
            for l in range(w):
                ww = i*f+j*(f+1)+k*(f+2)+l*(f+3)
                v = c[0][i] + c[1][j] + c[2][k] + c[3][l]
                if ww <= W: res = max(res, v)
                # print(ww,v)
print(res)

Submission status: Accepted

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

MINW = WV[0][0]

W0,W1,W2,W3 = [],[],[],[]
for w,v in WV:
    if w == MINW: W0.append(v)
    elif w == MINW + 1: W1.append(v)
    elif w == MINW + 2: W2.append(v)
    elif w == MINW + 3: W3.append(v)

W0.sort(reverse=True)
W1.sort(reverse=True)
W2.sort(reverse=True)
W3.sort(reverse=True)

W0 = [0] + W0
W1 = [0] + W1
W2 = [0] + W2
W3 = [0] + W3

from itertools import accumulate

W0 = list(accumulate(W0))
W1 = list(accumulate(W1))
W2 = list(accumulate(W2))
W3 = list(accumulate(W3))

ans = 0
for cnt0 in range(len(W0)):
    for cnt1 in range(len(W1)):
        for cnt2 in range(len(W2)):
            for cnt3 in range(len(W3)):
                SUMW = cnt0 * MINW
                SUMW += cnt1 * (MINW + 1)
                SUMW += cnt2 * (MINW + 2)
                SUMW += cnt3 * (MINW + 3)

                if SUMW <= W:
                    SUMV = W0[cnt0]
                    SUMV += W1[cnt1]
                    SUMV += W2[cnt2]
                    SUMV += W3[cnt3]
                    ans = max(ans, SUMV)

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n,W,*L=map(int,open(0).read().split())
l=[[] for _ in range(4)]
lim=[1]*4
m=min(L[::2])
for w,v in zip(*[iter(L)]*2):
	l[w-m].append(v)
	lim[w-m]+=1
ll=[]
for x in l:
	ll.append([0]+list(accumulate(sorted(x)[::-1])))
ans=0
for i in range(lim[0]):
	if m*i>W:
		continue
	for j in range(lim[1]):
		if m*i+(m+1)*j>W:
			continue
		for k in range(lim[2]):
			if m*i+(m+1)*j+(m+2)*k>W:
				continue
			for l in range(lim[3]):
				if m*i+(m+1)*j+(m+2)*k+(m+3)*l>W:
					continue
				ans=max(ans,ll[0][i]+ll[1][j]+ll[2][k]+ll[3][l])
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
list0 = []
list1 = []
list2 = []
list3 = []
for i in range(N):
    w,v = map(int,input().split())
    if i == 0:
        w1 = w
    if w == w1:
        list0.append(v)
    if w == w1 + 1:
        list1.append(v)
    if w == w1 + 2:
        list2.append(v)
    if w == w1 + 3:
        list3.append(v)
list0.sort(reverse = True)
list1.sort(reverse = True)
list2.sort(reverse = True)
list3.sort(reverse = True)
l0 = len(list0)
l1 = len(list1)
l2 = len(list2)
l3 = len(list3)
ans = 0
for i in range(min(l0,W//w1)+1):
    curw1 = W - w1*i
    for j in range(min(l1,curw1//(w1+1))+1):
        curw2 = curw1-(w1+1)*j
        for k in range(min(l2,curw2//(w1+2))+1):
            curw3 = curw2- (w1+2)*k
            l = min(l3,curw3//(w1+3))
            value = 0
            for a in range(i):
                value += list0[a]
            for a in range(j):
                value += list1[a]
            for a in range(k):
                value += list2[a]
            for a in range(l):
                value += list3[a]
            ans = max(ans,value)
print(ans)

Submission status: Accepted

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

N, W = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(N)]
w1 = wv[0][0]
dp = [[0] * 301 for _ in range(N+1)]
for w, v in wv:
    w -= w1
    for i in range(1, N+1)[::-1]:
        for j in range(w, 301):
            dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v)
ans = 0
for i in range(N+1):
    w = W - w1*i
    if w < 0:
        break
    ans = max(ans, dp[i][min(300, W-w1*i)])
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n,W,*L=map(int,open(0).read().split())
l=[[] for _ in range(4)]
lim=[1]*4
m=min(L[::2])
for w,v in zip(*[iter(L)]*2):
	l[w-m].append(v)
	lim[w-m]+=1
ll=[]
for x in l:
	ll.append([0]+list(accumulate(sorted(x)[::-1])))
ans=0
for i in range(lim[0]):
	for j in range(lim[1]):
		for k in range(lim[2]):
			for l in range(lim[3]):
				if m*i+(m+1)*j+(m+2)*k+(m+3)*l>W:
					continue
				ans=max(ans,ll[0][i]+ll[1][j]+ll[2][k]+ll[3][l])
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
WV = [tuple(map(int, input().split())) for _ in range(N)]
R = 3 * N + 10
INF = 10**18

w0 = WV[0][0]

dp = [[-INF] * R for _ in range(N + 1)]
dp[0][0] = 0

for w, v in WV:
    k = w - w0
    for n in range(N)[::-1]:
        for r in range(R)[::-1]:
            if r + k < R and dp[n + 1][r + k] < dp[n][r] + v:
                dp[n + 1][r + k] = dp[n][r] + v

ans = 0
for n in range(N + 1):
    for r in range(R):
        w = n * w0 + r
        if w <= W and dp[n][r] > ans:
            ans = dp[n][r]
print(ans)

Submission status: Accepted

Solution code:
N,W = list(map(int, input().split()))
w_0 = []
w_1 = []
w_2 = []
w_3 = []
v = []
w = 0
w_count = [0]*4
for _ in range(N):
    a,b = list(map(int, input().split()))
    if w == 0:
        w = a
        w_0.append(b)
    else:
        if a == w:
            w_0.append(b)
        elif a == w+1:
            w_1.append(b)
        elif a == w+2:
            w_2.append(b)
        elif a == w+3:
            w_3.append(b)
    w_count[a-w] += 1

w_0.sort(reverse=True)
w_1.sort(reverse=True)
w_2.sort(reverse=True)
w_3.sort(reverse=True)
ans = 0

for i in range(w_count[0]+1):
    for j in range(w_count[1]+1):
        for k in range(w_count[2]+1):
            for l in range(w_count[3]+1):
                if W >= w * i + (w+1) * j + (w+2) * k + (w+3) * l:
                  
                    S = sum(w_0[:i])+sum(w_1[:j])+sum(w_2[:k])+sum(w_3[:l])
                    ans = max(ans,S)

print(ans)




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

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

# k = max(dp)
# print(max(k))

Submission status: Accepted

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

from collections import defaultdict
from copy import copy

def main():
    n, wmax = map(int, input().split())
    dp = defaultdict(int)
    dp[0] = 0
    for i in range(n):
        w, v = map(int, input().split())
        dppre = copy(dp)
        for y in dppre:
            dp[y + w] = max(dp[y + w], dppre[y] + v)
    res = 0
    for y, z in dp.items():
        if y <= wmax:
            res = max(res, z)
    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#import sys
from collections import deque
import copy
#input=lambda :sys.stdin.readline().rstrip()
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

lst=deque([])
for w,v in WV:
    nlst=deque([[w,v]])
    for i in range(len(lst)):
        w1,v1=lst[i]
        if w1+w<=W:
            if w1:
                nlst.append([w1+w,v1+v])
    if not lst:
        lst=copy.copy(nlst)
        continue
    Xlst=lst
    lst=deque()

    if Xlst or nlst:
        w1,v1=nlst[0]
        w2,v2=Xlst[0]
        if w1<w2:
            lst.append(nlst.popleft())
        else:
            lst.append(Xlst.popleft())
    while Xlst or nlst:
        w,v=lst[-1]
        if Xlst and nlst:
            w1,v1=nlst[0]
            w2,v2=Xlst[0]

            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            elif w==w2:
                if v>=v2:
                    Xlst.popleft()
                else:
                    lst.pop()
                    lst.append(Xlst.popleft())
            else:
                if w1<w2:
                    if v>=v1:
                        nlst.popleft()
                    else:
                        lst.append(nlst.popleft())
                else:
                    if v>=v2:
                        Xlst.popleft()
                    else:
                        lst.append(Xlst.popleft())
        elif nlst:
            w1,v1=nlst[0]
            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            else:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.append(nlst.popleft())
        elif Xlst:
            nlst=Xlst
            Xlst=deque()



lst.append([0,0])
print(max([v for w,v in lst if w<=W]))

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
input=lambda :sys.stdin.readline().rstrip()
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

lst=deque([])
for w,v in WV:
    nlst=deque([[w,v]])
    for i in range(len(lst)):
        w1,v1=lst[i]
        if w1+w<=W:
            if w1:
                nlst.append([w1+w,v1+v])
    if not lst:
        lst=copy.copy(nlst)
        continue
    Xlst=lst
    lst=deque()

    if Xlst or nlst:
        w1,v1=nlst[0]
        w2,v2=Xlst[0]
        if w1<w2:
            lst.append(nlst.popleft())
        else:
            lst.append(Xlst.popleft())
    while Xlst or nlst:
        w,v=lst[-1]
        if Xlst and nlst:
            w1,v1=nlst[0]
            w2,v2=Xlst[0]

            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            elif w==w2:
                if v>=v2:
                    Xlst.popleft()
                else:
                    lst.pop()
                    lst.append(Xlst.popleft())
            else:
                if w1<w2:
                    if v>=v1:
                        nlst.popleft()
                    else:
                        lst.append(nlst.popleft())
                else:
                    if v>=v2:
                        Xlst.popleft()
                    else:
                        lst.append(Xlst.popleft())
        elif nlst:
            w1,v1=nlst[0]
            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            else:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.append(nlst.popleft())
        elif Xlst:
            nlst=Xlst
            Xlst=deque()



lst.append([0,0])
print(max([v for w,v in lst if w<=W]))

Submission status: Accepted

Solution code:
import sys
from collections import *
import copy
input=lambda :sys.stdin.readline().rstrip()
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

lst=deque([])
for w,v in WV:
    nlst=deque([[w,v]])
    for i in range(len(lst)):
        w1,v1=lst[i]
        if w1+w<=W:
            if w1:
                nlst.append([w1+w,v1+v])
    if not lst:
        lst=copy.copy(nlst)
        continue
    Xlst=lst
    lst=deque()

    if Xlst or nlst:
        w1,v1=nlst[0]
        w2,v2=Xlst[0]
        if w1<w2:
            lst.append(nlst.popleft())
        else:
            lst.append(Xlst.popleft())
    while Xlst or nlst:
        w,v=lst[-1]
        if Xlst and nlst:
            w1,v1=nlst[0]
            w2,v2=Xlst[0]

            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            elif w==w2:
                if v>=v2:
                    Xlst.popleft()
                else:
                    lst.pop()
                    lst.append(Xlst.popleft())
            else:
                if w1<w2:
                    if v>=v1:
                        nlst.popleft()
                    else:
                        lst.append(nlst.popleft())
                else:
                    if v>=v2:
                        Xlst.popleft()
                    else:
                        lst.append(Xlst.popleft())
        elif nlst:
            w1,v1=nlst[0]
            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            else:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.append(nlst.popleft())
        elif Xlst:
            nlst=Xlst
            Xlst=deque()



lst.append([0,0])
print(max([v for w,v in lst if w<=W]))

Submission status: Accepted

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *
input=lambda :sys.stdin.readline().rstrip()
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

lst=deque([])
for w,v in WV:
    nlst=deque([[w,v]])
    for i in range(len(lst)):
        w1,v1=lst[i]
        if w1+w<=W:
            if w1:
                nlst.append([w1+w,v1+v])
    if not lst:
        lst=copy.copy(nlst)
        continue
    Xlst=lst
    lst=deque()

    if Xlst or nlst:
        w1,v1=nlst[0]
        w2,v2=Xlst[0]
        if w1<w2:
            lst.append(nlst.popleft())
        else:
            lst.append(Xlst.popleft())
    while Xlst or nlst:
        w,v=lst[-1]
        if Xlst and nlst:
            w1,v1=nlst[0]
            w2,v2=Xlst[0]

            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            elif w==w2:
                if v>=v2:
                    Xlst.popleft()
                else:
                    lst.pop()
                    lst.append(Xlst.popleft())
            else:
                if w1<w2:
                    if v>=v1:
                        nlst.popleft()
                    else:
                        lst.append(nlst.popleft())
                else:
                    if v>=v2:
                        Xlst.popleft()
                    else:
                        lst.append(Xlst.popleft())
        elif nlst:
            w1,v1=nlst[0]
            if w==w1:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.pop()
                    lst.append(nlst.popleft())
            else:
                if v>=v1:
                    nlst.popleft()
                else:
                    lst.append(nlst.popleft())
        elif Xlst:
            nlst=Xlst
            Xlst=deque()



lst.append([0,0])
print(max([v for w,v in lst if w<=W]))

Submission status: Accepted

Solution code:
from itertools import accumulate
w=[[] for _ in range(4)]
N,W=map(int,input().split())
w1,v1=map(int,input().split())
w[0].append(v1)
for _ in range(N-1):
    wi,vi=map(int,input().split())
    w[wi-w1].append(vi)
for i in range(4):
    w[i].sort(reverse=True)
    w[i]=list(accumulate(w[i]))
ans=0
for i in range(len(w[0])+1):
    for j in range(len(w[1])+1):
        for k in range(len(w[2])+1):
            for l in range(len(w[3])+1):
                if w1*i+(w1+1)*j+(w1+2)*k+(w1+3)*l<=W:
                    su=0
                    if i>0:
                        su+=w[0][i-1]
                    if j>0:
                        su+=w[1][j-1]
                    if k>0:
                        su+=w[2][k-1]
                    if l>0:
                        su+=w[3][l-1]
                    ans=max(ans,su)
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""

dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N):
            if dp[i][n][j] == -1:continue
            dp[i+1][n+1][j+w] = max(dp[i][n][j] + v, dp[i][n][j+w])
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])

ans = 0
for i,a in enumerate(dp[N]):
    w = W - i*ws[0]
    if w >= 0:
        ans = max(ans,max(a[:w+1]))
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[-1]*(3*N+1) for i in range(N+1)]
dp[0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):    
    dp[i+1][:] = dp[i][:]
    for j in range(len(dp[i])):
        if dp[i][j] == -1:continue
        dp[i+1][j+w] = max(dp[i][j]+v, dp[i][j+w])
    # print(dp)

# print(dp[N][W-N*ws_m[0]])

dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    # print(i,w,v)
    for n in range(N):
        # dp[i+1][n][:] = dp[i][n][:]
        for j in range(N):
            if dp[i][n][j] == -1:continue
            if dp[i][n][j]+v >= dp[i][n][j+w]:
                # print("aa",i,n,j,v)
                dp[i+1][n+1][j+w] = dp[i][n][j] + v
            else:
                dp[i+1][n][j+w] = dp[i][n][j+w]
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
    # print(dp[i])

# for i in range(N+1):
    # print("i個選んだやつ",dp[N][i])
anss = dp[N]
a = 0
for i,ans in enumerate(anss):
    w = W - i*ws[0]
    if w >= 0:
        a = max(a,max(ans[:w+1]))
print(a)

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+10) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N):
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
            if dp[i][n][j] == -1: continue
            if j + (n+1)*ws[0] + w <= W:
                dp[i+1][n+1][j+w] = max(dp[i][n][j+w], dp[i][n][j] + v)

ans= 0
for i,As in enumerate(dp[N]):
    w = min(W - i*ws[0], sum(ws_m))
    if w >= 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+10) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N):
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
            # if dp[i][n][j] == -1: continue
            if j + (n+1)*ws[0] + w <= W:
                dp[i+1][n+1][j+w] = max(dp[i][n][j+w], dp[i][n][j] + v)

ans= 0
for i,As in enumerate(dp[N]):
    w = min(W - i*ws[0], sum(ws_m))
    if w >= 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

sum_ws_m = sum(ws_m)

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[0]*(3*N+10) for i in range(N+10)] for j in range(N+10)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N):
            # もらうDP
            # j-wなら、新しくwをナップサックに入れて価値が増えるか見る
            if ws[0]*(n+1)+j+w <= W:
                dp[i+1][n+1][j+w] = max(dp[i+1][n+1][j+w], dp[i][n][j]+v)
            # 追加できない場合は以前の情報を更新
                
            dp[i+1][n][j] = max( dp[i+1][n][j], dp[i][n][j] )
            # if dp[i][n][j] == -1: continue
            # # if j + n*ws[0] > W: continue
            # # print("check",i,n,j,v)    )
            # dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
            # dp[i+1][n+1][j+w] = max(dp[i][n+1][j+w], dp[i][n][j] + v)
        # print(dp[i+1][n])
ans= 0
for i,As in enumerate(dp[N]):
    w = min( W - i*ws[0], sum_ws_m )
    if w >= 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Accepted

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *
input=lambda :sys.stdin.readline().rstrip()
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]

lst=[]
for w,v in WV:
    for i in range(len(lst)):
        w1,v1=lst[i]
        if w1:
            lst.append([w1+w,v1+v])
    lst.append([w,v])

    lst=sorted(lst,key=lambda x:x[0],reverse=True)
    while lst and lst[-1][0]==0:
        lst.pop()

    w,v=lst[-1]
    for i in range(len(lst)-1)[::-1]:
        w1,v1=lst[i]
        if v1<=v:
            lst[i][0]=0
            lst[i][1]=0
        else:
            v=v1
    #print(lst)
print(max([v for w,v in lst if w<=W]))

Submission status: Accepted

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

dp=[[[-1 for i in range(0,3*N+1)] for j in range(0,N+1)] for k in range(0,N+1)]

for j in range(0,N+1):
    for k in range(0,3*N+1):
        weight=w[0]*j+k
        if weight>W:
            dp[0][j][k]=-1
        else:
            dp[0][j][k]=0
#i:何番までか　j:今までに何個選んだか　k:今までの重さ
for i in range(1,N+1):
    for j in range(0,N):
        for k in range(0,3*N+1):
            if 3*N>=k+w[i-1]-w[0]:
                if dp[i-1][j][k]==-1:
                    dp[i][j][k]=-1
                elif dp[i-1][j+1][k+w[i-1]-w[0]]==-1:
                    dp[i][j][k]=dp[i-1][j][k]
                else:
                    dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j+1][k+w[i-1]-w[0]]+v[i-1])
            else:
                dp[i][j][k]=dp[i-1][j][k]

if dp[N][0][0]==-1:
    print(0)
else:
    print(dp[N][0][0])

Submission status: Accepted

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
import sys
input = sys.stdin.readline
from heapq import*


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

for i in range(N):
    WV[i][0]-=Z
for n in range(N):
    for i in range(len(dp[0])):
        w,v=WV[n]
        if n==0:
            dp[n][w+301]=v
        else:
            dp[n][w+301]=max(dp[n-1][w+301],v)
            if i>=w+301:
                if dp[n-1][i-(w+301)]:
                    dp[n][i]=max(dp[n-1][i-(w+301)]+v,dp[n-1][i])
                else:
                    dp[n][i]=dp[n-1][i]
            else:
                dp[n][i]=dp[n-1][i]


print(max([max([dp[n][i] for i in range(len(dp[0])) if W>=i//301*Z+i%301]) for n in range(N)]))

Submission status: Accepted

Solution code:
n,weight=map(int,input().split())
ans=0
bag=[[] for i in range(4)]
W,V=map(int,input().split());bag[0].append((W,V))
for i in range(n-1):
    w,v=map(int,input().split())
    bag[w-W].append((w,v))
for i in range(4):
    bag[i].sort(key=lambda x:x[1],reverse=True)
valuesum=[[0 for i in range(len(bag[j])+1)] for j in range(4)]
for i in range(4):
    for j in range(len(bag[i])):
        valuesum[i][j+1]=valuesum[i][j]+bag[i][j][1]
for i in range(len(bag[0])+1):
    for j in range(len(bag[1])+1):
        for k in range(len(bag[2])+1):
            for l in range(len(bag[3])+1):
                if i*W+j*(W+1)+k*(W+2)+l*(W+3)>weight:continue
                if valuesum[0][i]+valuesum[1][j]+valuesum[2][k]+valuesum[3][l]>ans:
                    ans=valuesum[0][i]+valuesum[1][j]+valuesum[2][k]+valuesum[3][l]
print(ans)

Submission status: Accepted

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

def main():
    N,W = map(int,input().split())
    use = [[] for _ in range(4)]
    wc,v = map(int,input().split())
    use[0].append(v)
    for _ in range(N-1):
        w,v = map(int,input().split())
        use[w-wc].append(v)

    for i in range(4):
        use[i].sort(reverse = True)
        use[i] = [0]+use[i]
        l = len(use[i])
        for x in range(l-1):
            use[i][x+1] += use[i][x]

    ans = 0
    for i in range(min(len(use[3]),W//(wc+3)+1)):
        Wa = W-(wc+3)*i
        for j in range(min(len(use[2]),Wa//(wc+2)+1)):
            Wb = Wa-(wc+2)*j
            for k in range(min(len(use[1]),Wb//(wc+1)+1)):
                Wc = Wb-(wc+1)*k
                l = min(len(use[0])-1,Wc//wc)
                point = use[0][l]+use[1][k]+use[2][j]+use[3][i]
                ans = max(point,ans)
                
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,W=MI()
    WV=LLIN(N)
    W0 = WV[0][0]
    for i,(w,v) in enumerate(WV):
        WV[i][0] = w-W0
    WV.sort(key=lambda x: x[1], reverse=True)
    cumsum = [0]*N
    for i,(w,v) in enumerate(WV):
        cumsum[i]=cumsum[i-1]+v

    dp = [[0]*(N*3+1) for _ in range(N+1)]
    for i in range(N):
        for k in range(1,N+1)[::-1]:
            for w in range(N*3+1):
                if w>=WV[i][0]:
                    dp[k][w] = max(dp[k][w], dp[k-1][w-WV[i][0]] + WV[i][1])

    ans = 0 
    for k in range(1,N+1):
        W_k = W-W0*k
        if W_k>=N*3:
            ans = max(ans, cumsum[k-1])
            continue
        if W_k<0:
            break   
        ans = max(ans, dp[k][W_k])
    print(ans)



if __name__ == '__main__':
    main()