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:
# simple knapsack
n,W=map(int,input().split())
sacklist=[[]for i in range(4)]
w1=0
for _ in range(n):
    w,v=map(int,input().split())
    if _==0:
        w1=w
    sacklist[w-w1].append(v)

for i in range(4):
    sacklist[i].sort(reverse=True)
len1=len(sacklist[0])
len2=len(sacklist[1])
len3=len(sacklist[2])
len4=len(sacklist[3])
sumlist1=[]
sumlist2=[]
sumlist3=[]
sumlist4=[]
for _ in range(len1+1):
    sumlist1.append(sum(sacklist[0][:_]))
for _ in range(len2+1):
    sumlist2.append(sum(sacklist[1][:_]))
for _ in range(len3+1):
    sumlist3.append(sum(sacklist[2][:_]))
for _ in range(len4+1):
    sumlist4.append(sum(sacklist[3][:_]))
l1=len(sumlist1)
l2=len(sumlist2)
l3=len(sumlist3)
l4=len(sumlist4)
answer=0
for i in range(l1):
    for j in range(l2):
        for k in range(l3):
            for m in range(l4):
                if ((w1)*i+(w1+1)*j+(w1+2)*k+(w1+3)*m)<= W:
                    answer=max(answer,sumlist1[i]+sumlist2[j]+sumlist3[k]+sumlist4[m])
print(answer)

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
data=[[] for i in range(4)]
w1=wv[0][0]
for u in wv:
    w,v=u
    data[w-w1].append(v)
for i in range(4):
    data[i].sort(reverse=True)
    data[i]=[0]+data[i]
    for j in range(1,len(data[i])):
        data[i][j]+=data[i][j-1]
a=len(data[0])
b=len(data[1])
c=len(data[2])
d=len(data[3])
ans=0
for i in range(a):
    for j in range(b):
        for k in range(c):
            for l in range(d):
                if w1*i+(w1+1)*j+(w1+2)*k+(w1+3)*l<=W:
                    ans=max(ans,data[0][i]+data[1][j]+data[2][k]+data[3][l])
print(ans)

Submission status: Accepted

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

w = [[] for _ in range(4)]
w1, v1 = map(int, input().split())
w[0].append(v1)
for _ in range(N - 1):
    a, b = map(int, input().split())
    w[a - w1].append(b)

for i in range(4):
    w[i].sort(reverse = True)
    for j in range(1, len(w[i])):
        w[i][j] += w[i][j - 1]

# print (w)
ans = 0
for a in range(len(w[0]) + 1):
    if a == 0:
        v_a = 0
    else:
        v_a = w[0][a - 1]
    for b in range(len(w[1]) + 1):
        if b == 0:
            v_b = 0
        else:
            v_b = w[1][b - 1]
        for c in range(len(w[2]) + 1):
            if c == 0:
                v_c = 0
            else:
                v_c = w[2][c - 1]
            cost = a * w1 + b * (w1 + 1) + c * (w1 + 2)
            if cost > W:
                pass
            else:
                lest = W - cost
                d = min(lest // (w1 + 3), len(w[3]))
                # print (d)
                if d == 0:
                    v_d = 0
                else:
                    v_d = w[3][d - 1]

                ans = max(ans, v_a + v_b + v_c + v_d)

print (ans)

Submission status: Accepted

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())
V=[[] for _ in [0]*4]
for i in range(N):V[w[i]-w[0]].append(v[i])
for i in range(4):
    V[i].sort(reverse=True)
    for j in range(len(V[i])-1):V[i][j+1]+=V[i][j]
    V[i].insert(0,0)

a=0
for i in range(len(V[0])):
    for j in range(len(V[1])):
            for k in range(len(V[2])):
                for l in range(len(V[3])):
                    if i*w[0]+j*-~w[0]+k*-~-~w[0]+l*-~-~-~w[0]<=W:a=max(a,V[0][i]+V[1][j]+V[2][k]+V[3][l])
print(a)

Submission status: Accepted

Solution code:
n,l=map(int,input().split())
dic={0:0}
for _ in range(n):
  w,v=map(int,input().split())
  tmp=sorted(list(dic.keys()),reverse=True)
  for key in tmp:
    if key+w not in dic:
      dic[key+w]=dic[key]+v
    else:
      dic[key+w]=max(dic[key]+v,dic[key+w])
tmp=sorted(list(dic.keys()))
ans=0
for key in tmp:
  if key>l:
    break
  ans=max(ans,dic[key])
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
w=[0]*n 
v=[0]*n
from collections import Counter
l=[]
for i in range(n):
    a,b=map(int,input().split())
    w[i]=a  
    v[i]=b 
a=min(w)
c=Counter(w)
#print(a)
cnt1=c[a]
#print(c)
v1=[v[i] for i in range(n) if w[i]==a]
v1.sort(reverse=1)
cnt2=c[a+1]
v2=[v[i] for i in range(n) if w[i]==a+1]
cnt3=c[a+2]
v3=[v[i] for i in range(n) if w[i]==a+2]
v2.sort(reverse=1)
v3.sort(reverse=1)
cnt4=c[a+3]
v4=[v[i] for i in range(n) if w[i]==a+3]
v4.sort(reverse=1)
#print(cnt1)
pv1=[0]*(cnt1+1)
pv1[0]=0
for i in range(1,cnt1+1):
    pv1[i]=pv1[i-1]+v1[i-1]
pv2=[0]*(cnt2+1)  
pv2[0]=0
for i in range(1,cnt2+1):
    pv2[i]=pv2[i-1]+v2[i-1]
pv3=[0]*(cnt3+1) 
pv3[0]=0
for i in range(1,cnt3+1):
    pv3[i]=pv3[i-1]+v3[i-1]
ans=0 
pv4=[0]*(cnt4+1)
for i in range(1,cnt4+1):
    pv4[i]=pv4[i-1]+v4[i-1]
for i in range(0,cnt1+1):
    for j in range(0,cnt2+1):
        for k in range(0,cnt3+1):
            for z in range(0,cnt4+1):
                if (i)*a+(j)*(a+1)+(k)*(a+2)+z*(a+3)<=m:
                    ans=max(ans,pv1[i]+pv2[j]+pv3[k]+pv4[z])
print(ans)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
list_item = []
for _ in range(n):
  weight, value = map(int, input().split())
  list_item.append((weight, value))

dict_ks = {}
dict_ks[0] = 0
num_checked = 0
while num_checked < n:
  new_w, new_v = list_item[num_checked]
  for temp_w, temp_v in list(dict_ks.items()):
    if temp_w + new_w <= w:
      if temp_w + new_w not in dict_ks:
        dict_ks[temp_w + new_w] = temp_v + new_v
      else:
        dict_ks[temp_w + new_w] = max(dict_ks[temp_w + new_w], temp_v + new_v)
  num_checked += 1

print(max(dict_ks.values()))

Submission status: Accepted

Solution code:
from collections import defaultdict
n,m=map(int,input().split())
d=defaultdict(int)
d[0]=0
for _ in range(n):
       w,u=map(int,input().split())
       for i,j in d.copy().items():
              if i+w<=m:d[i+w]=max(d[i+w],j+u)
print(max(d.values()))

Submission status: Accepted

Solution code:

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

dic = {}
dic[0] = 0

for i in range(N):

    odic = dic.copy()

    w,v = map(int,input().split())

    for j in odic:

        if j + w not in dic and j+w <= W:
            dic[j+w] = odic[j] + v

        elif j+w <= W:
            dic[j+w] = max(odic[j]+v,dic[j+w])

ans = 0

for i in dic:
    ans = max(ans,dic[i])

print (ans)

Submission status: Accepted

Solution code:
import collections

n, w = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(n)]

dp = [collections.defaultdict(lambda: 0) for _ in range(n + 1)]
dp[0][0] = 0
for i, (w0, v0) in enumerate(ls):
    for w1, v1 in dp[i].items():
        if w1 <= w:
            dp[i + 1][w1] = max(dp[i + 1][w1], v1)
        if w0 + w1 <= w:
            if w0 + w1 in dp[i].keys():
                dp[i + 1][w0 + w1] = max(dp[i + 1][w0 + w1], dp[i][w0 + w1],
                                         v0 + v1)
            else:
                dp[i + 1][w0 + w1] = v0 + v1
print(max(dp[n].values()))

Submission status: Accepted

Solution code:
from itertools import accumulate
N, W = map(int, input().split())
Item = [[] for i in range(4)]
for i in range(N):
    wi, vi = map(int, input().split())
    if i == 0:
        Item[0].append(vi)
        w_base = wi
    else:
        Item[wi - w_base].append(vi)

w0, w1, w2, w3 = Item
w0 = [0] + list(accumulate(sorted(w0, reverse=True)))
w1 = [0] + list(accumulate(sorted(w1, reverse=True)))
w2 = [0] + list(accumulate(sorted(w2, reverse=True)))
w3 = [0] + list(accumulate(sorted(w3, reverse=True)))

ans = 0
for i in range(len(w0)):
    for j in range(len(w1)):
        for k in range(len(w2)):
            tmp_weight = w_base * i + (w_base + 1) * j + (w_base + 2) * k
            if tmp_weight > W:
                continue
            tmp_ans = w0[i] + w1[j] + w2[k] + w3[min((W - tmp_weight) // (w_base + 3), len(w3) - 1)]
            ans = max(ans, tmp_ans)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n, limit = LI()
weight = []
value = []
for w, v in LIR(n):
    weight += [w]
    value += [v]


w1 = min(weight)
w2, w3, w4 = w1 + 1, w1 + 2, w1 + 3
w1_list = [0] + list(accumulate(sorted([value[i] for i in range(n) if weight[i] == w1], reverse=True)))
w2_list = [0] + list(accumulate(sorted([value[i] for i in range(n) if weight[i] == w2], reverse=True)))
w3_list = [0] + list(accumulate(sorted([value[i] for i in range(n) if weight[i] == w3], reverse=True)))
w4_list = [0] + list(accumulate(sorted([value[i] for i in range(n) if weight[i] == w4], reverse=True)))


ans = 0
for i, j, k, l in product(range(len(w1_list)), range(len(w2_list)), range(len(w3_list)), range(len(w4_list) )):
    if i * w1 + j * w2 + k * w3 + l * w4 > limit:
        continue
    ans = max(ans, w1_list[i] + w2_list[j] + w3_list[k] + w4_list[l])



print(ans)

Submission status: Accepted

Solution code:
# ABC060D - Simple Knapsack (ARC073D)
from itertools import accumulate as acc


def main():
    N, W, *A = map(int, open(0).read().split())
    V, x = [[] for _ in range(4)], A[0]  # x: w1 (W1 ≤ wi ≤ w1 + 3)
    for w, v in zip(*[iter(A)] * 2):  # group by weight
        V[w - x].append(v)
    for i in range(4):  # V[i][j] := max value of picking up j items from group i
        V[i] = tuple(acc([0] + sorted(V[i], reverse=1)))
    L = [len(v) for v in V]
    ans = 0
    for i in range(L[0]):
        for j in range(L[1]):
            for k in range(L[2]):
                w = i * x + j * (x + 1) + k * (x + 2)
                if w > W:
                    break
                l = min(L[3] - 1, (W - w) // (x + 3))
                v = V[0][i] + V[1][j] + V[2][k] + V[3][l]
                ans = max(ans, v)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

    base_w = wv[0][0]
    dic = {wv[0][0]:[], wv[0][0]+1:[], wv[0][0]+2:[], wv[0][0]+3:[]}
    for i in range(N):
        w, v = wv[i]
        dic[w].append(v)
    
    # python3.7.2だと奇跡的に辞書型が宣言順になってたけど，
    # python3.4.3だと順序が保証されないのでちゃんとソートしないとだめ!
    wv = sorted(list(dic.items()))
    tmp = [None for i in range(4)]
    for i in range(4):
        num, l = wv[i]
        l = sorted(l, reverse=True)
        for j in range(1, len(l)):
            l[j] += l[j-1]
        tmp[i] = [0] + l

    # for i in range(4):
    #     print(tmp[i][:10])

    ans = 0
    for i in range(len(tmp[0])):
        for j in range(len(tmp[1])):
            for k in range(len(tmp[2])):
                for l in range(len(tmp[3])):
                    weight = base_w * i + (base_w + 1) * j + (base_w + 2) * k + (base_w + 3) * l
                    if weight <= W:
                        val = tmp[0][i] + tmp[1][j] + tmp[2][k] + tmp[3][l]
                        if ans < val:
                            ans = val
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

    base_w = wv[0][0]
    dic = {wv[0][0]:[], wv[0][0]+1:[], wv[0][0]+2:[], wv[0][0]+3:[]}
    for i in range(N):
        w, v = wv[i]
        dic[w].append(v)
    
    wv = sorted(list(dic.items()))
    tmp = [None for i in range(4)]
    for i in range(4):
        num, l = wv[i]
        l = sorted(l, reverse=True)
        for j in range(1, len(l)):
            l[j] += l[j-1]
        tmp[i] = [0] + l

    # for i in range(4):
    #     print(tmp[i][:10])

    ans = 0
    for i in range(len(tmp[0])):
        for j in range(len(tmp[1])):
            for k in range(len(tmp[2])):
                for l in range(len(tmp[3])):
                    weight = base_w * i + (base_w + 1) * j + (base_w + 2) * k + (base_w + 3) * l
                    if weight <= W:
                        val = tmp[0][i] + tmp[1][j] + tmp[2][k] + tmp[3][l]
                        if ans < val:
                            ans = val
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

w0 = V[0][0]

V_split = [[] for i in range(4)]
for i in range(n):
    V_split[V[i][0] - w0].append(V[i][1])

for i in range(4):
    V_split[i].sort(reverse=True)

# print(V_split)

V_split_S = [[0] for i in range(4)]
for i in range(4):
    for j in range(len(V_split[i])):
        V_split_S[i].append(V_split_S[i][-1] + V_split[i][j])

# print(V_split)
# print(V_split_S)


ans = 0

for i in range(min(len(V_split_S[0]), w//w0 + 1)):
    wi = w - w0 * i
    for j in range(min(len(V_split_S[1]), wi//(w0+1) + 1)):
        wj = wi - (w0+1) * j
        for k in range(min(len(V_split_S[2]), wj//(w0+2) + 1)):
            wk = wj - (w0+2) * k
            l = min(len(V_split_S[3]), wk//(w0+3) + 1) - 1
            
            ans = max(ans, V_split_S[0][i] + V_split_S[1][j] + V_split_S[2][k] + V_split_S[3][l])
            # print(i,j,k,l, ans)
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wvs = []
for i in range(N):
  w, v = map(int, input().split())
  wvs.append((w, v))
w0 = wvs[0][0]
vs0 = []
vs1 = []
vs2 = []
vs3 = []
for w, v in wvs:
  if w == w0:
    vs0.append(v)
  if w == w0+1:
    vs1.append(v)
  if w == w0+2:
    vs2.append(v)
  if w == w0+3:
    vs3.append(v)
vs0.sort(reverse=True)
vs1.sort(reverse=True)
vs2.sort(reverse=True)
vs3.sort(reverse=True)
#print(w0, vs0, vs1, vs2, vs3)
rs = [0]
for i0 in range(len(vs0)+1):
  for i1 in range(len(vs1)+1):
    for i2 in range(len(vs2)+1):
      for i3 in range(len(vs3)+1):
        if w0*i0+(w0+1)*i1+(w0+2)*i2+(w0+3)*i3 <= W:
          r = sum(vs0[:i0])+sum(vs1[:i1])+sum(vs2[:i2])+sum(vs3[:i3])
          rs.append(r)
r = max(rs)
print(r)

Submission status: Accepted

Solution code:
N,W,*L=map(int,open(0).read().split())
w1=L[0]
l=[[] for _ in range(4)]
for w,v in zip(*[iter(L)]*2):
	l[w-w1].append(v)
l=[sorted(t)[::-1] for t in l]
a,b,c,d=map(len,l)
ans=0
for h in range(a+1):
	for i in range(b+1):
		for j in range(c+1):
			for k in range(d+1):
				if w1*h+(w1+1)*i+(w1+2)*j+(w1+3)*k<=W:
					ans=max(ans,sum(l[0][:h]+l[1][:i]+l[2][:j]+l[3][:k]))
print(ans)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
l1,l2,l3,l4=[],[],[],[]
a=l[0][0]
for i in range(n):
    if l[i][0]==a:
        l1.append(l[i][1])
    elif l[i][0]==a+1:
        l2.append(l[i][1])
    elif l[i][0]==a+2:
        l3.append(l[i][1])
    else:
        l4.append(l[i][1])
l1.sort(reverse=True)
l2.sort(reverse=True)
l3.sort(reverse=True)
l4.sort(reverse=True)
ans=0
for h in range(len(l1)+1):
    for i in range(len(l2)+1):
        for j in range(len(l3)+1):
            for k in range(len(l4)+1):
                if a*h+(a+1)*i+(a+2)*j+(a+3)*k<=w:
                    ans=max(ans,sum(l1[:h])+sum(l2[:i])+sum(l3[:j])+sum(l4[:k]))
print(ans)

Submission status: Accepted

Solution code:
import collections
def main():

    N, W = map(int, input().split())
    goods = collections.defaultdict(list)
    for _ in range(N):
        w, v = map(int, input().split())
        goods[w].append(v)

    for w in goods:
        goods[w].sort(reverse = True)

    cur = dict()
    cur[0] = 0
    for w in goods:
        temp = cur.copy()
        for w1 in temp:
            w2, v2 = w1, temp[w1]
            for i in range(len(goods[w])):
                w2 += w
                v2 += goods[w][i]
                if w2 <= W:
                    if w2 not in cur:
                        cur[w2] = v2
                    else:
                        cur[w2] = max(cur[w2], v2)
    max_v = 0
    for w in cur:
        max_v = max(max_v, cur[w])
    return max_v

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
# ABC060D - Simple Knapsack (ARC073D)
# exhaustive search
from itertools import accumulate


def main():
    N, W, *A = map(int, open(0).read().split())
    V, x = [[] for _ in range(4)], A[0]  # x: w1 (W1 ≤ wi ≤ w1 + 3)
    for i in range(0, 2 * N, 2):  # group by weight
        w, v = A[i : i + 2]
        V[w - x] += [v]
    for i in range(4):  # V[i][j] := max value of picking up j items from group i
        V[i] = tuple(accumulate([0] + sorted(V[i], reverse=1)))
    L = [len(v) for v in V]
    ans = 0
    for i in range(L[0]):
        for j in range(L[1]):
            for k in range(L[2]):
                w = i * x + j * (x + 1) + k * (x + 2)
                if w > W:
                    break
                l = min(L[3] - 1, (W - w) // (x + 3))
                v = V[0][i] + V[1][j] + V[2][k] + V[3][l]
                ans = max(ans, v)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
L=[[] for i in range(4)]
L2=[[0] for i in range(4)]
for i in range(n):
  L[l[i][0]-l[0][0]].append(l[i][1])
for i in range(4):
  L[i].sort()
  L[i].reverse()
for i in range(4):
  for j in range(len(L[i])):
    L2[i].append(L2[i][len(L2[i])-1]+L[i][j])
ansL=[]
for i1 in range(len(L2[0])):
  for i2 in range(len(L2[1])):
    for i3 in range(len(L2[2])):
      for i4 in range(len(L2[3])):
        if l[0][0]*i1+(l[0][0]+1)*i2+(l[0][0]+2)*i3+(l[0][0]+3)*i4<=w:
          ansL.append(L2[0][i1]+L2[1][i2]+L2[2][i3]+L2[3][i4])
print(max(ansL))

Submission status: Accepted

Solution code:
from itertools import accumulate

def chk(samp):
    for i in samp:
        print(samp)

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]

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



#価値毎に置き換える
wl = [[] for i in range(4)]

#価値ごとのりすとに入れていく
for i in range(N):
    wl[w[i]-w[0]].append(v[i])


#ソートして最初に0を追加する。0は選択しない場合
for i in range(4):
    wl[i].sort(reverse = 1)
    wl[i].insert(0,0)
    

#累積和を作る
for i in range(4):
    wl[i] = list(accumulate(wl[i]))
    
#出力用変数
out = 0


for i,wl0 in enumerate(wl[0]):
   for j,wl1 in enumerate(wl[1]):
       for k,wl2 in enumerate(wl[2]):
           for l,wl3 in enumerate(wl[3]):
               if i*(w[0])+j*(w[0]+1)+k*(w[0]+2)+l*(w[0]+3) > W:
                   pass
               else:
                   out = max(out,wl0+wl1+wl2+wl3)
                   
print(out)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, W = map(int, input().split())
V = [[] for _ in range(4)]
w0, v0 = map(int, input().split())
V[0].append(v0)
for _ in range(N - 1):
    w, v = map(int, input().split())
    V[w - w0].append(v)
S = []
for v in V:
    v.sort(reverse=True)
    S.append([0] + list(accumulate(v)))
ans = 0
for i, si in enumerate(S[0]):
    for j, sj in enumerate(S[1]):
        for k, sk in enumerate(S[2]):
            for l, sl in enumerate(S[3]):
                if w0 * i + (w0 + 1) * j + (w0 + 2) * k + (w0 + 3) * l > W:
                    continue
                ans = max(ans, si + sj + sk + sl)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

n, w = map(int, input().split())
obj = [list(map(int, input().split())) for _ in range(n)]

dp = [defaultdict(int), defaultdict(int)]
dp[0][0] = 0
for i in range(n):
    wi, vi = obj[i]
    # print(dp[i%2])
    dp[(i+1)%2] = dp[i%2].copy()
    for w0 in dp[i%2]:
        # dp[(i+1)%2][w0] = dp[i%2][w0]
        if w0 + wi <= w:
            dp[(i+1)%2][w0 + wi] = max(dp[(i+1)%2][w0 + wi], dp[i%2][w0] + vi)

# print(dp[n%2])
print(max(dp[n%2].values()))

Submission status: Accepted

Solution code:
from collections import defaultdict

def cumsum(ls):
    for i in range(1,len(ls)):
        ls[i] += ls[i-1]
    ls.insert(0,0)
    return ls

def main():
    n,w = map(int,input().split())
    dc = defaultdict(list)
    W1,V1 = map(int,input().split())
    dc[W1].append(V1)
    for _ in range(1,n):
        wk,vk = map(int,input().split())
        dc[wk].append(vk)

    #　下準備
    dc = sorted(dc.items(),key=lambda x:x[0],reverse=True)
    for i in range(len(dc)):
        dc[i] = list(dc[i])
        dc[i][1] = cumsum(sorted(list(dc[i][1]),reverse=True))
    
    for i in range(4-len(dc)):
        dc.append([0,[0]])
    can = [0,0] # [w,v]
    ans = 0
    for i in range(len(dc[0][1])):
        for j in range(len(dc[1][1])):
            for k in range(len(dc[2][1])):
                for l in range(len(dc[3][1])):
                    can[0] = dc[0][0]*i + dc[1][0]*j + dc[2][0]*k + dc[3][0]*l
                    can[1] = dc[0][1][i] + dc[1][1][j] + dc[2][1][k]+ dc[3][1][l]
                    if can[0]<=w:
                        ans = max(ans,can[1])
                    can = [0,0]
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LS()
    if a[-1] == b[0] and b[-1] == c[0]:
        print("YES")
    else:
        print("NO")
    return

#B
def B():
    a, b, c = LI()
    for i in range(1, b):
        if a * i % b == c:
            print("YES")
            return
    print("NO")
    return

#C
def C():
    _, T = LI()
    t = LI()
    ans = 0
    now = t[0]
    for i in t[1:]:
        if now + T <= i:
            ans += T
        else:
            ans += i - now
        now = i
    print(ans + T)

    return

#D
def D():
    n, W = LI()
    wv = LIR(n)
    wv.sort()
    dp = [-inf] * ((3 * n + 1) * n + 1)
    dp[0] = 0
    minw =  wv[0][0]
    if minw <= 3 * n:
        for w, v in wv:
            for i in range((3 * n + 1) * n, w - 1, -1):
                dp[i] = max(dp[i - w] + v, dp[i])
        print(max(dp[:W + 1]))
    else:
        for w, v in wv:
            w -= minw
            for i in range(min(W // minw, n - 1), 0, -1):
                for k in range(3 * n, w - 1, -1):
                    dp[(3 * n + 1) * i + k] = max(dp[(3 * n + 1) * (i - 1) + k - w] + v, dp[(3 * n + 1) * i + k])
        print(max(dp[:W // minw * (3 * n + 1) + W % minw + 1]))
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):

    V = [[0] for _ in range(4)]
    for ww, vv in zip(w, v):
        V[ww-w[0]].append(vv)
    V = [[0]+list(accumulate(sorted(v, reverse=True))) for v in V]

    m = 0
    M = N+1
    for i in range(M):
        if i*w[0] > W:
            break
        if len(V[0]) <= i:
            break
        for j in range(M-i):
            if i*w[0] + j*(w[0]+1) > W:
                break
            if len(V[1]) <= j:
                break
            for k in range(M-i-j):
                if i*w[0] + j*(w[0]+1) + k*(w[0]+2) > W:
                    break
                if len(V[2]) <= k:
                    break
                for l in range(M-i-j-k):
                    if i*w[0] + j*(w[0]+1) + k*(w[0]+2) + l*(w[0]+3) > W:
                        break
                    if len(V[3]) <= l:
                        break
                    tot = V[0][i]+V[1][j]+V[2][k]+V[3][l]
                    m = max(m, tot)
    print(m)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,W,*A=map(int,open(0).read().split());d={0:0}
while A:
 v,w=A.pop(),A.pop()
 for x,y in d.copy().items():
  if x+w<=W:d[x+w]=max(d.get(x+w,0),y+v)
print(max(d.values()))

Submission status: Accepted

Solution code:
N,W,*A=map(int,open(0).read().split());d={0:0}
for w,v in zip(A[::2],A[1::2]):
 for x,y in d.copy().items():
  if x+w<=W:d[x+w]=max(d.get(x+w,0),y+v)
print(max(d.values()))

Submission status: Accepted

Solution code:
N,W=map(int,input().split());d={0:0}
for _ in [0]*N:
 w,v=map(int,input().split())
 for x,y in d.copy().items():
  if x+w<=W:d[x+w]=max(d.get(x+w,0),y+v)
print(max(d.values()))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
d = {0:0}
for _ in range(N):
  w, v = map(int, input().split())
  for dw, dv in d.copy().items():
    if dw + w <= W:
      d[dw + w] = max(d.get(dw + w, 0), dv + v)
print(max(d.values()))

Submission status: Accepted

Solution code:
N, WW = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(N)]
W, V = zip(*l)
M = [{} for i in range(N + 1)]
def cal(i, w):
  if w in M[i]:
    return M[i][w]
  if i == N:
    v = 0
  elif w < W[i]:
    v = cal(i + 1, w)
  else:
    v = max(cal(i + 1, w), cal(i + 1, w - W[i]) + V[i])
  M[i][w] = v
  return v

print(cal(0, WW))

Submission status: Accepted

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

N, WW = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(N)]
W, V = zip(*l)
M = [{} for i in range(N + 1)]
def cal(i, w):
  if w in M[i]:
    return M[i][w]
  if i == N:
    v = 0
  elif w < W[i]:
    v = cal(i + 1, w)
  else:
    v = max(cal(i + 1, w), cal(i + 1, w - W[i]) + V[i])
  M[i][w] = v
  return v

print(cal(0, WW))

Submission status: Accepted

Solution code:

import bisect
import collections
import itertools


def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]


def partial_sum(xs):
    if not xs:
        return [0]
    ys = [0, xs[0][1]]
    for i in range(1, len(xs)):
        xs[i][1] += xs[i-1][1]
        ys.append(xs[i][1])
    return ys

n,w=getints()
items=getint2d(n)
w0 = items[0][0]
kind0=list(sorted(filter(lambda s: s[0] == w0,     items), reverse=True))
kind1=list(sorted(filter(lambda s: s[0] == w0 + 1, items), reverse=True))
kind2=list(sorted(filter(lambda s: s[0] == w0 + 2, items), reverse=True))
kind3=list(sorted(filter(lambda s: s[0] == w0 + 3, items), reverse=True))

kind0 = partial_sum(kind0)
kind1 = partial_sum(kind1)
kind2 = partial_sum(kind2)
kind3 = partial_sum(kind3)



res = 0

for n0 in range(len(kind0)):
    for n1 in range(len(kind1)):
        for n2 in range(len(kind2)):
            for n3 in range(len(kind3)):
                weight = n0*w0 + n1*(w0+1) + n2*(w0+2) + n3*(w0+3)
                if weight > w: continue
                tmp = kind0[n0] + kind1[n1] + kind2[n2] + kind3[n3]
                res = max(res, tmp)

print(res)

Submission status: Accepted

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

items = [[] for _ in range(4)]
w0, v0 = map(int, input().split())
items[0].append(v0)

for _ in range(N - 1):
    w, v = map(int, input().split())
    items[w - w0].append(v)

for i in range(4):
    items[i].sort(reverse=True)

sumItems = [[0 for _ in range(len(items[i]) + 1)] for i in range(4)]

for i in range(4):
    for j, v in enumerate(items[i]):
        sumItems[i][j + 1] = sumItems[i][j] + v

ans = 0
for firstCount in range(len(items[0]) + 1):
    for secondCount in range(len(items[1]) + 1):
        for thirdCount in range(len(items[2]) + 1):
            for forthCount in range(len(items[3]) + 1):
                sumWeight = w0 * firstCount + (w0 + 1) * secondCount + (w0 + 2) * thirdCount + (w0 + 3) * forthCount
                if sumWeight > W:
                    break
                sumV = 0
                for i, count in enumerate([firstCount, secondCount, thirdCount, forthCount]):
                    sumV += sumItems[i][count]
                ans = max(ans, sumV)

print(ans)