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:
N, W = map(int, input().split())

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

w0 = items[0][1]
itemGrp = [[] for _ in range(4)]
for v, w in items:
    itemGrp[w - w0].append(v)

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

accItemGrp = []
for i in range(4):
    item = itemGrp[i]
    accValue = [0] * (len(item) + 1)
    for i in range(1, len(item) + 1):
        accValue[i] = accValue[i - 1] + item[i - 1]
    accItemGrp.append(accValue)

ans = 0
for n0 in range(len(itemGrp[0]) + 1):
    for n1 in range(len(itemGrp[1]) + 1):
        for n2 in range(len(itemGrp[2]) + 1):
            for n3 in range(len(itemGrp[3]) + 1):
                weight = (n0 + n1 + n2 + n3) * w0 + n1 + 2 * n2 + 3 * n3
                if weight <= W:
                    value = 0
                    for i, n in enumerate([n0, n1, n2, n3]):
                        value += accItemGrp[i][n]
                    ans = max(ans, value)

print(ans)

Submission status: Accepted

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

wvs = [[] for i in range(4)]
w0 = WV[0][0]
for w,v in WV:
    wvs[w-w0].append(v)

cumwvs = []
for vs in wvs:
    cums = [0]
    for v in sorted(vs, reverse=True):
        cums.append(cums[-1] + v)
    cumwvs.append(cums)

ans = 0
for i,a in enumerate(cumwvs[0]):
    if i*w0 > W: break
    for j,b in enumerate(cumwvs[1]):
        if i*w0 + j*(w0+1) > W: break
        for k,c in enumerate(cumwvs[2]):
            if i*w0 + j*(w0+1) + k*(w0+2) > W: break
            for l,d in enumerate(cumwvs[3]):
                if i*w0 + j*(w0+1) + k*(w0+2) + l*(w0+3) > W: break
                ans = max(ans, a+b+c+d)
print(ans)

Submission status: Accepted

Solution code:
n, W = map(int, input().split())
dp = [[[0] * 301 for _ in range(n + 1)] for _ in range(n + 1)]
li = [list(map(int, input().split())) for _ in range(n)]
p = li[0][0]
for i, x in enumerate(li):
    w, v = x
    w -= p
    for j in range(i + 1):
        for k in range(301):
            if k >= w:
                if dp[i][j][k - w] + v > dp[i][j + 1][k]:
                    dp[i + 1][j + 1][k] = dp[i][j][k - w] + v
                else:
                    dp[i + 1][j + 1][k] = dp[i][j + 1][k]
            else:
                dp[i + 1][j + 1][k] = dp[i][j + 1][k]
ans = 0
for i in range(n + 1):
    for k in range(301):
        if i * p + k <= W:
            ans = max(dp[n][i][k], ans)
print(ans)

Submission status: Accepted

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

Wdic = {}
for w in WV:
  if w[0] not in Wdic:
    Wdic[w[0]] = [w]
  else:
    Wdic[w[0]].append(w)

Wcount = [[0 for _ in range(2)] for _ in range(4)]
idx = 0
for k in Wdic.keys():
  Wcount[idx] = [k,len(Wdic[k])]
  idx += 1
#print(Wcount)

Wsum = {}
for k,v in Wdic.items():
  v.sort(key=lambda x:x[1], reverse = True)
  Wsum[k] = [v[0][1]]
  for i in range(1,len(v)):
    Wsum[k].append(Wsum[k][-1] + v[i][1])
#print(Wsum)

def check(i,j,k,l):
  ret = 0
  w = 0
  if i > 0 and Wcount[0][0] > 0:
    ret += Wsum[Wcount[0][0]][i-1]
    w += Wcount[0][0]*i
  if j > 0 and Wcount[1][0] > 0:
    ret += Wsum[Wcount[1][0]][j-1]
    w += Wcount[1][0]*j
  if k > 0 and Wcount[2][0] > 0:
    ret += Wsum[Wcount[2][0]][k-1]
    w += Wcount[2][0]*k
  if l > 0 and Wcount[3][0] > 0:
    ret += Wsum[Wcount[3][0]][l-1]
    w += Wcount[3][0]*l
  if w > W:
    ret = 0
  return ret

value = 0
for i in range(Wcount[0][1]+1):
  for j in range(Wcount[1][1]+1):
    for k in range(Wcount[2][1]+1):
      for l in range(Wcount[3][1]+1):
        value = max(value,check(i,j,k,l))
print(value)

Submission status: Accepted

Solution code:


N,WW = list(map(int,input().split(" ")))

things = [list(map(int,input().split(" "))) for _ in range(N )]
W,v = things[0]
dic = {}
dic[W] = [v]
for i in range(1,4):
    dic[W + i] = []
for temp in things[1:]:
    w,v = temp
    dic[w].append(v)
ans = 0
l1 = len(dic[W])
l2 = len(dic[W + 1])
l3 = len(dic[W + 2])
l4 = len(dic[W + 3])
dic[W].sort(reverse=True)
dic[W + 1].sort(reverse=True)
dic[W + 2].sort(reverse=True)
dic[W + 3].sort(reverse=True)
for i1 in range(l1 + 1):
    for i2 in range(l2 + 1):
        for i3 in range(l3 + 1):
            for i4 in range(l4 + 1):
                temp = sum(dic[W][:i1]) + sum(dic[W+1][:i2]) + sum(dic[W+2][:i3]) + sum(dic[W+ 3][:i4])

                if  W * i1 +  (W +1) * i2 + (W +2) * i3 +  (W +3) * i4 <= WW:
                    ans = max(temp,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import bisect
import itertools

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def LI_(): return([int(x)-1 for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    N,W = LI()
    dic = {}
    dic[0] = 0

    for i in range(N):
        w,v = LI()
        dic_nxt = {k:dic[k] for k in dic}
        for k in dic:
            if k+w<=W:
                dic_nxt[k+w] = max(dic_nxt.get(k+w,0),dic.get(k,0)+v)
        dic = {k:dic_nxt[k] for k in dic_nxt}
    return(max(dic.values()))

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

Submission status: Accepted

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

from collections import defaultdict
List = []
dp = []*(N+1)
for i in range(N+1):
    dp.append(defaultdict(lambda : -float("inf")))
for i in range(N+1):
    dp[i][0] = 0
#print(dp)

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

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

Submission status: Accepted

Solution code:
#D問題
N,W = map(int,input().split())
WV = [list(map(int,input().split())) for i in range(N)]


w1 = WV[0][0]
WV.sort()

vlist = [[] for i in range(4)]
for i in range(N):
    w,v = WV[i][0],WV[i][1]
    d = w-w1
    vlist[d].append(v)
    
vrui = [[0] for i in range(4)]
for i in range(4):
    vlist[i].sort(reverse=True)
    for v in vlist[i]:
        vrui[i].append(vrui[i][-1]+v)
        
#print(vlist)
#print(vrui)
MAX = 0
for i in range(min(N+1,len(vlist[0])+1)):
    for j in range(min(N-i+1,len(vlist[1])+1)):
        for k in range(min(N-i-j+1,len(vlist[2])+1)):
            for l in range(min(N-(i+j+k)+1,len(vlist[3])+1)):
                #print(i,j,k,l)
                #print(w1*i+(w1+1)*j+(w1+2)*k+(w1+3)*l)
                #print(vrui[0][i],vrui[1][j],vrui[2][k],vrui[3][l])
                if (w1*i+(w1+1)*j+(w1+2)*k+(w1+3)*l) <= W:
                    MAX = max(MAX,(vrui[0][i]+vrui[1][j]+vrui[2][k]+vrui[3][l]))

print(MAX)

Submission status: Accepted

Solution code:

N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
w0 = wv[0][0]
weights = [wv[0][0],wv[0][0]+1,wv[0][0]+2,wv[0][0]+3]
wdict = {}
cnt = 0
for w in weights:
    wdict[w] = cnt
    cnt += 1
values = [[] for _ in range(4)]

for w,v in wv:
    values[wdict[w]].append(v)

sums = 0
for i in range(4):
    values[i].sort(reverse = True)
    sums += sum(values[i])
    
ruisekiwa = [[0]*(N+1) for _ in range(4)]
for i in range(4):
    ruisekiwa[i][0] = 0
    for j in range(1,len(values[i])+1):
        ruisekiwa[i][j] = ruisekiwa[i][j-1] + values[i][j-1] 
    
ans = 0
for i in range(len(values[0])+1):
    for j in range(len(values[1])+1):
        for k in range(len(values[2])+1):
            for l in range(len(values[3])+1):
                w_tmp = w0*i + (w0+1)*j + (w0+2)*k + (w0+3) * l

                if w_tmp <= W:
                    val = ruisekiwa[0][i] + ruisekiwa[1][j] + ruisekiwa[2][k] + ruisekiwa[3][l]
                    ans = max(ans,val)
                    
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, W = map(int, input().split())
w_0, v_0 = map(int, input().split())
v_list = [[] for _ in range(4)]
v_list[0].append(v_0)

for _ in range(N - 1):
    w_in, v_in = map(int, input().split())
    v_list[w_in - w_0].append(v_in)
v_list = [[0] + list(accumulate(sorted(v, reverse=True))) for v in v_list]
ans = 0

#print(v_list)

for i in range(len(v_list[0])):
    for j in range(len(v_list[1])):
        for k in range(len(v_list[2])):
            for l in range(len(v_list[3])):
                if (i * w_0) + (j * (w_0 + 1)) + (k * (w_0 + 2)) + (l * (w_0 + 3)) <= W:
                    ans = max(ans, v_list[0][i] + v_list[1][j] + v_list[2][k] + v_list[3][l])
                else:
                    break
print(ans)

Submission status: Accepted

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

V = [[] for _ in range(4)]
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        w0 = w
        V[0].append(v)
    else:
        V[w-w0].append(v)
J = []
for i in range(4):
    F = sorted(V[i], reverse=True)
    G = [0]
    for f in F:
        G.append(f+G[-1])
    J.append(G)

ans = 0
for s0 in range(len(J[0])):
    for s1 in range(len(J[1])):
        for s2 in range(len(J[2])):
            for s3 in range(len(J[3])):
                if s0*w0 + s1*(w0+1) + s2*(w0+2) + s3*(w0+3) > W:
                    continue
                ans = max(ans, J[0][s0]+J[1][s1]+J[2][s2]+J[3][s3])
print(ans)

Submission status: Accepted

Solution code:
# ARC073D - Simple Knapsack (ABC060D)
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):
        w, v = A[i : i + 2]
        V[w - x] += [v]
    for i in range(4):
        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]):
                for l in range(L[3]):
                    w = i * x + j * (x + 1) + k * (x + 2) + l * (x + 3)
                    if w > W:
                        break
                    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:
# ARC073D - Simple Knapsack (ABC060D)
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):
        w, v = A[i : i + 2]
        V[w - x] += [v]
    for i in range(4):
        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:
from itertools import accumulate
n, w = map(int, input().split())
w_0, v_0 = map(int, input().split())
v_list = [[] for _ in range(4)]
v_list[0].append(v_0)
for _ in range(n - 1):
    w_in, v_in = map(int, input().split())
    v_list[w_in - w_0].append(v_in)
v_list = [[0] + list(accumulate(sorted(v, reverse=True))) for v in v_list]
ans = 0
for i in range(len(v_list[0])):
    for j in range(len(v_list[1])):
        for k in range(len(v_list[2])):
            for l in range(len(v_list[3])):
                if ((i) * w_0) + ((j) * (w_0 + 1)) + ((k) * (w_0 + 2)) + (((l) * (w_0 + 3))) <= w:
                    ans = max(ans, v_list[0][i] + v_list[1][j] + v_list[2][k] + v_list[3][l])
                else:
                    break
print(ans)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
v=[[] for i in range(4)]
# print(v)
for i in range(n):
    v[wv[i][0]-wv[0][0]].append(wv[i][1])
# print(v)
for i in range(4):
    v[i].sort(reverse=True)
# print(v)
ans=0
for i in range(len(v[0])+1):
    tmp=[[0,0] for t in range(4)]        
    tmp[0][0]=sum(v[0][:i])
    tmp[0][1]=wv[0][0]*i
    for j in range(len(v[1])+1):
        tmp[1][0]=sum(v[1][:j])
        tmp[1][1]=(wv[0][0]+1)*j
        for k in range(len(v[2])+1):
            tmp[2][0]=sum(v[2][:k])
            tmp[2][1]=(wv[0][0]+2)*k
            for l in range(len(v[3])+1):
                tmp[3][0]=sum(v[3][:l])
                tmp[3][1]=(wv[0][0]+3)*l
                if tmp[0][1]+tmp[1][1]+tmp[2][1]+tmp[3][1]<=w:
                    ans=max(ans,tmp[0][0]+tmp[1][0]+tmp[2][0]+tmp[3][0])
print(ans)

Submission status: Accepted

Solution code:
n,W = map(int,input().split())
w1,v = map(int,input().split())
c = [[] for _ in range(4)]
c[0].append(v)
for i in range(n-1):
    w,v = map(int,input().split())
    c[w-w1].append(v)

for i in c:
    i.sort(reverse=True)
#print(c)
l = [len(c[i]) for i in range(4)]
sum_c = []
for _ in range(4):
    k = [0]
    for i in range(l[_]):
        k.append(k[-1] + c[_][i])
    sum_c.append(k)
ans = 0
for p1 in range(l[0]+1):
    for p2 in range(l[1]+1):
        for p3 in range(l[2]+1):
            for p4 in range(l[3]+1):
                now = w1*p1+(w1+1)*p2+(w1+2)*p3+(w1+3)*p4
                if now<=W:
                    ans = max(ans,sum_c[0][p1]+sum_c[1][p2]+sum_c[2][p3]+sum_c[3][p4])
                    #print(p1,p2,p3,p4)


print(ans)

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(N)]
dp=[{} for i in range(N+1)]
dp[0][0]=0
for i in range(N):
    p=dp[i].keys()
    for w in p:
        dp[i+1][w]=dp[i][w]
    for w in p:
        wn=w+wv[i][0]
        if wn<=W and (wn not in dp[i+1] or dp[i+1][wn]<dp[i][w]+wv[i][1]):
                dp[i+1][wn]=dp[i][w]+wv[i][1]
print(max(dp[N].values()))

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
goods=[[] for i in range(4)]
w1=-1
for i in range(N):
    w,v=map(int,input().split())
    if i==0:
        w1=w
    goods[w-w1].append(v)
S=[]
for x in range(4):
    goods[x].sort(reverse=True)
    G=goods[x]
    now=[0]*(len(G)+1)
    for i in range(len(G)):
        now[i+1]=now[i]+G[i]
    S.append(now)
ans=0
for i in range(1+len(goods[0])):
    for j in range(1+len(goods[1])):
        for k in range(1+len(goods[2])):
            wnow=W-w1*(i+j+k)-j-2*k
            if wnow<0:
                continue
            else:
                ans=max(ans,S[0][i]+S[1][j]+S[2][k]+S[3][min(len(S[3])-1,wnow//(w1+3))])
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

from itertools import accumulate

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n, w = li()
value = {i: [] for i in range(4)}

for i in range(n):
    wei, val = li()

    if i == 0:
        w0 = wei

    value[wei - w0].append(val)

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

    value[i] = [0] + list(accumulate(value[i]))


ans = 0

for i in range(len(value[0])):
    for j in range(len(value[1])):
        for k in range(len(value[2])):
            rest = w - i*w0 - j*(w0+1) - k*(w0+2)
            x = rest // (w0+3)

            if x < 0:
                continue
            else:
                ans = max(ans, value[0][i] + value[1][j] + value[2][k] + value[3][min(len(value[3])-1, x)])

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,w=map(int,input().split())

w1,v1=map(int,input().split())
W,V=[0],[v1]
for i in range(n-1):
  wi,vi=map(int,input().split())
  W.append(wi-w1)
  V.append(vi)
DP=[[[0]*(n+1) for _ in range(3*n+1)] for __ in range(n+1)]
for i in range(1,n+1):
  for j in range(3*i+1):
    for k in range(1,i+1):
      if j<W[i-1]:
        DP[i][j][k]=DP[i-1][j][k]
      else:
        DP[i][j][k]=max(DP[i-1][j-W[i-1]][k-1]+V[i-1],DP[i-1][j][k])
ans=0
for j in range(3*n+1):
  for k in range(n+1):
    if j+w1*k<=w:
      ans=max(ans,DP[n][j][k])
print(ans)

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
wv=[]
for i in range(N):
    a,b=map(int,input().split())
    wv.append((a,b))
if wv[0][0]<300:
    dp=[[0]*(30000+1) for i in range(N+1)]
    for i in range(1,N+1):
        wi,vi=wv[i-1]
        for j in range(1,30000+1):
            dp[i][j]=dp[i-1][j]
            if j-wi<0:
                continue
            dp[i][j]=max(dp[i-1][j-wi]+vi,dp[i][j])
    ans=dp[N][W]
    print(ans)
    quit()
dp=[[0]*(301*101) for i in range(N+1)]
d=wv[0][0]
def change(n):
    return 301*(n//d)+min(n%d,300)
#if change(W)>301*101:
#    quit()
for i in range(1,N+1):
    wi,vi=wv[i-1]
    z=301+(wi-d)
    for j in range(1,301*101):
        dp[i][j]=dp[i-1][j]
        if j-z<0:
            continue

        dp[i][j]=max(dp[i-1][j-z]+vi,dp[i][j])
ans=dp[N][change(W)]
print(ans)

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w0,v=map(int,input().split())
goods=[[v],[],[],[]]
for i in range(N-1):
    w,v=map(int,input().split())
    goods[w-w0].append(v)
val=[]
for x in range(4):
    goods[x].sort(reverse=True)
    valx=[0]*(len(goods[x])+1)
    for k in range(len(goods[x])):
        valx[k+1]=valx[k]+goods[x][k]
    val.append(valx)
ans=0
for i in range(len(goods[0])+1):
    if w0*i>W:
        break
    for j in range(len(goods[1])+1):
        if w0*(i+j)+j>W:
            break
        for k in range(len(goods[2])+1):
            if w0*(i+j+k)+j+2*k>W:
                break
            for l in range(len(goods[3])+1):
                if w0*(i+j+k+l)+j+2*k+3*l>W:
                    break
                ans=max(ans,val[0][i]+val[1][j]+val[2][k]+val[3][l])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate, product

# 各重さごとに価値降順でソート
# とっていく
# 重さ合計は w0 * k ~ (w0 + 3) * kのどれか N=100だと15000通りくらい

def solve(N: int, W: int, ws: "List[int]", vs: "List[int]"):
    w0 = ws[0]
    items = [[] for _ in range(4)]
    accum = [[] for _ in range(4)]
    for w, v in zip(ws, vs):
        items[w-w0].append(v)
    for i in range(4):
        items[i].sort(reverse=True)
        accum[i] = [0] + list(accumulate(items[i]))
    count = [len(items[i]) for i in range(4)]
    
    res = 0
    for nums in product(*[range(count[i] + 1) for i in range(4)]):
        w = sum((w0+i) * nums[i] for i in range(4))
        if w > W:
            continue
        v = sum(accum[i][nums[i]] for i in range(4))
        res = max(v, res)
    
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate, product

# 入力
N, W = map(int, input().split())
w, v = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), ())
)

# 各重さの物のリスト（価値について降順）
u = [
    [0] + list(
        accumulate(
            sorted(
                (
                    y for x, y in zip(w, v)
                    if x == i
                ),
                reverse=True
            )
        )
    )
    for i in range(w[0], w[0] + 4)
]

# 重さが w_1, w_1 + 1, w_1 + 2 の物をa, b, c 個選んだとき、
# 重さが w_1 + 3 の物の選び方は一意に定まることを用いて最適値を求める
ans = max(
    sum(u[i][k] for i, k in enumerate(t)) +
    u[3][
        min(
            len(u[3]) - 1,
            (W - sum(k * (w[0] + i) for i, k in enumerate(t))) // (w[0] + 3)
        )
    ]
    for t in product(*map(range, map(len, u[:3])))
    if sum(k * (w[0] + i) for i, k in enumerate(t)) <= W
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
n,w = map(int, input().split())

a = [list(map(int, input().split())) for i in range(n)]

x = a[0][0]

for i in range(n):
    a[i][0]-=x

dp = [[[0 for i in range(301)] for j in range(n+1)] for k in range(n+1)]

for k in range(1,n+1):
    for j in range(1,n+1):
        for i in range(301):
            if i>=a[k-1][0]:
                dp[k][j][i]=max(dp[k-1][j-1][i-a[k-1][0]] + a[k-1][1], dp[k-1][j][i])
            else:
                dp[k][j][i]=dp[k-1][j][i]

ans = 0
for j in range(n+1):
    for i in range(301):
        if i+j*x<=w:
            ans = max(ans,dp[n][j][i])

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**10
from functools import reduce

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

memo = {}

def nap(i, j):# // i番目までの品物から重さの和がj以下なるように選んだときの、取りうる価値の総和の最大値を返す関数
    if i == 0:
        return 0

    if (i, j) in memo:
        return memo[i, j]
    elif j < w[i-1]:
        temp = nap(i-1, j)
    else:
        temp = max(nap(i-1, j), nap(i-1, j-w[i-1]) + v[i-1])

    memo[i,j] = temp

    return memo[i,j]

print(nap(N, W))

Submission status: Accepted

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

L=[[]for i in range(4)]

A=[]
for i in range(N):
    w,v=map(int,input().split())
    A.append([w,v])
A.sort()
#print(A)

L[0].append(A[0])
P=0
for i in range(1,N):
    if A[i][0]==A[i-1][0]:
        L[P].append(A[i])
    else:
        P+=1
        L[P].append(A[i])
#print(L)
for i in range(4):
    L[i].sort(reverse=True)
#print(L)
S=[]
for i in range(4):
    s=[0]
    for j in range(len(L[i])):
        s.append(s[j]+L[i][j][1])
    S.append(s)
#print(S)
we=[0,0,0,0]
for i in range(4):
    if L[i]==[]:
        pass
    else:
        we[i]=L[i][0][0]
ans=0
for a in range(len(S[0])):
    for b in range(len(S[1])):
        for c in range(len(S[2])):
            for d in range(len(S[3])):
                v=S[0][a]+S[1][b]+S[2][c]+S[3][d]
                w=we[0]*a+we[1]*b+we[2]*c+we[3]*d
                if W>=w and ans<v:
                    ans=v
print(ans)

Submission status: Accepted

Solution code:
from collections import*
import functools
import sys
input=sys.stdin.readline
@functools.lru_cache(maxsize=None)
def Knapsack(N,W):
    for i in range(N):
        w,v=map(int,input().split())
        for k,b in d.copy().items():
            if k+w<=W:
                d[k+w]=max(d[k+w],b+v)
    return print(max(d.values()))
N,W=map(int,input().split())   #pypyで実行！
d=defaultdict(int)
d[0]=0
if __name__=='__main__':
  Knapsack(N,W)

Submission status: Accepted

Solution code:
from collections import*
import functools
import sys
input=sys.stdin.readline
@functools.lru_cache(maxsize=None)
def Knapsack(N,W):
    for i in range(N):
        w,v=map(int,input().split())
        for k,b in d.copy().items():
            if k+w<=W:
                d[k+w]=max(d[k+w],b+v)
    return max(d.values())
N,W=map(int,input().split())   #pypyで実行！
d=defaultdict(int)
d[0]=0
print(Knapsack(N,W))

Submission status: Accepted

Solution code:
import itertools
n,w = map(int,input().split())

d = dict()
p = dict()
for i in range(n):
    u,v = map(int,input().split())
    if d.__contains__(u):
        d[u]+=1
    else:
        d[u]=1
    if p.__contains__(u):
        p[u].append(v)
    else:
        p[u]=[v]

for k in p.keys():
    p[k].sort(reverse=True)
    acc = [0]
    for c in p[k]:
        acc.append(acc[-1]+c)
    p[k]=acc

d = list(d.items())
p = [p[item[0]] for item in d]
g = [item[0] for item in d]
d = [range(item[1]+1)for item in d]
res = 0
for t in itertools.product(*d):
    if(sum([g[i]*t[i] for i in range(len(t))])<=w):
        res = max(res,sum([p[i][t[i]] for i in range(len(t))]))
print(res)

Submission status: Accepted

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

N, W = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
memo = {i : {} for i in range(N)}

def dfs(i, j):
    if i == N:
        return 0
    elif j in memo[i]:
        return memo[i][j]
    elif A[i][0] > j:
        ans = dfs(i + 1, j)
    else:
        ans  = max(dfs(i + 1, j), A[i][1] + dfs(i + 1, j - A[i][0]))
    memo[i][j] = ans
    return ans
        
print(dfs(0, W))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
vs = [[] for _ in range(4)]
w1, v1 = map(int, input().split())
vs[0].append(v1)
for i in range(N - 1):
    w, v = map(int, input().split())
    vs[w - w1].append(v)
#print(vs)
s = [[0] for _ in range(4)]
for i in range(4):
    vs[i].sort()
    for j in range(len(vs[i])):
        s[i].append(s[i][-1] + vs[i][-j-1])
#print(vs)
ans = 0
for i in range(N + 1):
    if i > len(vs[0]):
        break
    if i * w1 > W:
        break
    si = s[0][i]
    for j in range(N + 1 - i):
        if j > len(vs[1]):
            break
        if i * w1 + j * (w1 + 1) > W:
            break
        sj = si
        sj += s[1][j]
        for k in range(N + 1 - i - j):
            if k > len(vs[2]):
                break
            if i * w1 + j * (w1 + 1) + k * (w1 + 2) > W:
                break
            sk = sj
            sk += s[2][k]
            for l in range(N + 1 - i - j - k):
                if l > len(vs[3]):
                    break
                if i * w1 + j * (w1 + 1) + k * (w1 + 2) + l * (w1 + 3) > W:
                    break
                sl = sk
                sl += s[3][l]
                ans = max(ans, sl)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, W = map(int, input().split())
dp = defaultdict(int)
dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for pw, pv in dp.copy().items():
        if pw + w <= W:
            dp[pw + w] = max(dp[pw + w], pv + v)

print(max(dp.values()))

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
wd = {}
minw, v = map(int, input().split())
wd[minw] = [v]
wd[minw+1] = []
wd[minw+2] = []
wd[minw+3] = []
for _  in range(n-1):
  _w, v = map(int, input().split())
  wd[_w].append(v)

for k, v in wd.items():
  wd[k] = list(sorted(v))[::-1]

maxw = 0
for i in range(w // minw + 1):
  for j in range((w - minw * i) // (minw + 1) + 1):
    for k in range((w - minw * i - (minw + 1) * j) // (minw + 2) + 1):
      l = (w - minw * i - (minw + 1) * j - (minw + 2) * k) // (minw + 3)
      tmp = sum(wd[minw][:i]) + sum(wd[minw+1][:j]) + sum(wd[minw+2][:k]) + sum(wd[minw+3][:l])
      if tmp > maxw:
        maxw = tmp
print(maxw)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
di = dict()
m = 0
for _ in range(n):
  x,y = map(int, input().split())
  if x not in di:
    di[x] = []
  di[x].append(y)
for i in di:
  di[i].sort(reverse=True)
a = min(di.keys())
b,c,d = a+1,a+2,a+3
for i in b,c,d:
  if i not in di:
    di[i] = []
for i in range(len(di[a])+1):
  for j in range(len(di[b])+1):
    for k in range(len(di[c])+1):
      for l in range(len(di[d])+1):
        if i*a + j*b + k*c + l*d <= w:
          m = max(m, sum(di[a][:i] + di[b][:j] + di[c][:k] + di[d][:l]))
print(m)

Submission status: Accepted

Solution code:
n,w = map(int, input().split())
w4 = [[] for i in range(4)]
w1 = None
for i in range(n):
    ws, vs = map(int,input().split())
    if i == 0:
        w1 = ws
    ws -= w1
    w4[ws].append(vs)

for i in range(4):
    w4[i].sort(reverse=True)
    tmp = [0]
    for j in w4[i]:
        tmp.append(tmp[-1]+j)
    w4[i] = tmp
ans = 0
for i in range(len(w4[0])):
    for j in range(len(w4[1])):
        for k in range(len(w4[2])):
            for l in range(len(w4[3])):
                if w >= w1*(i+j+k+l) + j + 2*k + 3*l:
                    ans = max(ans, w4[0][i]+w4[1][j]+w4[2][k]+w4[3][l])
print(ans)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())

dp = [[[-1]*4*n for j in range(n+1)] for i in range(n+1)]
dp[0][0][0] = 0
w1 = None
for i in range(n):
    ws, vs = map(int, input().split())
    if i == 0:
        w1 = ws
    ws -= w1
    for j in range(i+2):
        for k in range(4*n):
            if j-1 >= 0 and k-ws >= 0 and dp[i][j-1][k-ws] >= 0:
                dp[i+1][j][k] = max(dp[i][j][k], dp[i][j-1][k-ws]+vs)
            else:
                dp[i+1][j][k] = dp[i][j][k]

ans = 0
for j in range(n+1):
    for k in range(4*n):
        if w1*j + k <= w:
            ans = max(ans, dp[-1][j][k])
print(ans)