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:
import sys
input = sys.stdin.readline
from itertools import accumulate

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

MINW = WV[0][0]

# それぞれの重さについての価値のリスト
W0 = sorted([0] + [v for w,v in WV if w == MINW])
W1 = sorted([0] + [v for w,v in WV if w == MINW+1])
W2 = sorted([0] + [v for w,v in WV if w == MINW+2])
W3 = sorted([0] + [v for w,v in WV if w == MINW+3])

# 累積和
W0 = tuple(accumulate(W0))
W1 = tuple(accumulate(W1))
W2 = tuple(accumulate(W2))
W3 = tuple(accumulate(W3))

ans = 0
for w0 in range(len(W0)):
    for w1 in range(len(W1)):
        for w2 in range(len(W2)):
            for w3 in range(len(W3)):
                # tmp: 状態(w0,w1,w2,w3)での重さ
                tmp = (len(W0) - (w0 + 1)) * MINW
                tmp += (len(W1) - (w1 + 1)) * (MINW+1)
                tmp += (len(W2) - (w2 + 1)) * (MINW+2)
                tmp += (len(W3) - (w3 + 1)) * (MINW+3)

                # ナップサックに入る場合
                if tmp <= W:
                    # tmp: 価値の総和
                    tmp = W0[-1] - W0[w0]
                    tmp += W1[-1] - W1[w1]
                    tmp += W2[-1] - W2[w2]
                    tmp += W3[-1] - W3[w3]
                    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

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

MINW = WV[0][0]

W0 = sorted([0] + [v for w,v in WV if w == MINW])
W1 = sorted([0] + [v for w,v in WV if w == MINW+1])
W2 = sorted([0] + [v for w,v in WV if w == MINW+2])
W3 = sorted([0] + [v for w,v in WV if w == MINW+3])

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

ans = 0
for w0 in range(len(W0)):
    for w1 in range(len(W1)):
        for w2 in range(len(W2)):
            for w3 in range(len(W3)):
                tmp = (len(W0) - (w0 + 1)) * MINW
                tmp += (len(W1) - (w1 + 1)) * (MINW+1)
                tmp += (len(W2) - (w2 + 1)) * (MINW+2)
                tmp += (len(W3) - (w3 + 1)) * (MINW+3)

                if tmp <= W:
                    tmp = W0[-1] - W0[w0]
                    tmp += W1[-1] - W1[w1]
                    tmp += W2[-1] - W2[w2]
                    tmp += W3[-1] - W3[w3]
                    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, W = (int(i) for i in input().split())
    WV = [[int(i) for i in input().split()] for j in range(N)]
    for i in range(1, N):
        WV[i][0] -= WV[0][0]
    w_base = WV[0][0]
    WV[0][0] = 0
    V = {i: [0] for i in range(4)}
    for w, v in WV:
        V[w].append(v)
    for i in range(4):
        V[i].sort(reverse=True)
    ans = 0
    from itertools import product
    for p in product(range(len(V[0])), range(len(V[1])),
                     range(len(V[2])), range(len(V[3]))):
        w_cur = w_base*p[0] + (w_base+1)*p[1] + \
            (w_base+2)*p[2] + (w_base+3)*p[3]
        if W < w_cur:
            continue
        ans = max(ans, sum(sum(V[i][:min(p[i], len(V[i]))]) for i in range(4)))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, W = (int(i) for i in input().split())
    WV = [[int(i) for i in input().split()] for j in range(N)]
    for i in range(1, N):
        WV[i][0] -= WV[0][0]
    w0 = WV[0][0]
    WV[0][0] = 0
    V = {i: [] for i in range(4)}
    for w, v in WV:
        V[w].append(v)
    for i in range(4):
        V[i].sort(reverse=True)
    S = [[0] for i in range(4)]
    for i in range(4):
        for b in V[i]:
            S[i].append(S[i][-1] + b)
    ans = 0
    for i, v0 in enumerate(S[0]):
        for j, v1 in enumerate(S[1]):
            for k, v2 in enumerate(S[2]):
                for m, v3 in enumerate(S[3]):
                    w_cur = w0*(i+j+k+m) + j + 2*k + 3*m
                    if W < w_cur:
                        continue
                    ans = max(ans, v0+v1+v2+v3)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

N, W = map(int, input().split())
d = {i: [] for i in range(4)}
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        w0 = w
    w -= w0
    d[w].append(v)

wv = [[] for _ in range(4)]
for k, v in d.items():
    v.sort(reverse=True)
    v = [0] + v
    wv[k] = tuple(accumulate(v))

# w1をc1こ入れる
# w2をc2個入れる...
ans = 0
for c0, v0 in enumerate(wv[0]):
    for c1, v1 in enumerate(wv[1]):
        for c2, v2 in enumerate(wv[2]):
            for c3, v3 in enumerate(wv[3]):
                weight = w0 * (c0 + c1 + c2 + c3) + c1 + c2 * 2 + c3 * 3
                val = v0 + v1 + v2 + v3
                if weight > W:
                    continue
                ans = max(ans, val)

print(ans)

Submission status: Accepted

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

w = L[0][0]
M = 0
for i in range(N):
    M += L[i][0]-w
dp = [[[0]*(M+1) for _ in range(N+1)] for _ in range(N+1)]
t = 0
for i in range(N):
    t += L[i][0]-w
    for j in range(i+2):
        for k in range(t+1):
            if j*w+k < L[i][0]:
                dp[i+1][j][k] = dp[i][j][k]
            else:
                dp[i+1][j][k] = max(dp[i][j][k], dp[i][j-1][k-(L[i][0]-w)]+L[i][1])

ans = 0
for j in range(N+1):
    for k in range(M+1):
        if j*w+k <= W:
            ans = max(ans, dp[N][j][k])
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
WV = [tuple(map(int,input().split())) for i in range(N)]
w0 = WV[0][0]
a = [[],[],[],[]]
for w,v in WV:
    i = w-w0
    a[i].append(v)
for i in range(4):
    a[i].sort(reverse=True)
c = [[0] for _ in range(4)]
for i in range(4):
    for b in a[i]:
        c[i].append(c[i][-1] + b)

ans = 0
for i,v0 in enumerate(c[0]):
    for j,v1 in enumerate(c[1]):
        for k,v2 in enumerate(c[2]):
            for l,v3 in enumerate(c[3]):
                w = w0*(i+j+k+l) + j + k*2 + l*3
                if w>W: break
                ans = max(ans, v0+v1+v2+v3)
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(N)]
w1 = wv[0][0]
l1, l2, l3, l4 = [], [], [], []

for wi, vi in wv:
    if wi==w1:
        l1.append(vi)
    elif wi==w1+1:
        l2.append(vi)
    elif wi==w1+2:
        l3.append(vi)
    else:
        l4.append(vi)

l1.sort(reverse=True)
l2.sort(reverse=True)
l3.sort(reverse=True)
l4.sort(reverse=True)

l1_acc = [0]
l2_acc = [0]
l3_acc = [0]
l4_acc = [0]

for l1_i in l1:
    l1_acc.append(l1_acc[-1]+l1_i)

for l2_i in l2:
    l2_acc.append(l2_acc[-1]+l2_i)

for l3_i in l3:
    l3_acc.append(l3_acc[-1]+l3_i)

for l4_i in l4:
    l4_acc.append(l4_acc[-1]+l4_i)

ans = 0

for i in range(len(l1)+1):
    for j in range(len(l2)+1):
        for k in range(len(l3)+1):
            for l in range(len(l4)+1):
                if w1*i+(w1+1)*j+(w1+2)*k+(w1+3)*l<=W:
                    ans = max(ans, l1_acc[i]+l2_acc[j]+l3_acc[k]+l4_acc[l])
    
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
N,W = map(int,input().split())
w = [[] for i in range(4)]
w1,v1 = map(int,input().split())
w[0].append(v1)
for i in range(N-1):
    wi,vi = map(int,input().split())
    w[wi-w1].append(vi)
num = []
for i in range(4):
    w[i].sort(reverse= 1)
    w[i] = [0]+list(accumulate(w[i]))
    num.append(len(w[i]))
ans = 0
for n1 in range(num[0]):
    for n2 in range(num[1]):
        for n3 in range(num[2]):
            for n4 in range(num[3]):
                wc = w1*(n1+n2+n3+n4) + n2 + 2*n3 + 3*n4
                if wc <= W:
                    vc = w[0][n1]+w[1][n2]+w[2][n3]+w[3][n4]
                    ans = max(ans,vc)
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
w = [[] for i in range(4)]
w1,v1 = map(int,input().split())
w[0].append(v1)
for i in range(N-1):
    wi,vi = map(int,input().split())
    w[wi-w1].append(vi)
num = []
for i in range(4):
    w[i].sort(reverse= 1)
    num.append(len(w[i]))
ans = 0
for n1 in range(num[0]+1):
    for n2 in range(num[1]+1):
        for n3 in range(num[2]+1):
            for n4 in range(num[3]+1):
                wc = w1*(n1+n2+n3+n4) + n2 + 2*n3 + 3*n4
                if wc <= W:
                    vc = sum(w[0][:n1])+sum(w[1][:n2])+sum(w[2][:n3])+sum(w[3][:n4])
                    ans = max(ans,vc)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_right

N,W = LI()
w,v = LIR(N,2)

w_list = []
for i in range(N+1):
    for j in range(i*w[0],i*(w[0]+3)+1):
        w_list.append(j)
w_list = sorted(list(set(w_list)))
M = len(w_list)

d = {}
temp = 0
for wl in w_list:
    d[temp] = wl
    temp += 1

dp = [[0]*M for _ in range(N)]
for i in range(N):
    for j in range(M):
        dp[i][j] = dp[i-1][j]
        x = d[j]-w[i]
        if x >= 0:
            p = bisect_right(w_list,x)
            dp[i][j] = max(dp[i][j], dp[i-1][p-1]+v[i])

p = bisect_right(w_list,W)
print(dp[N-1][p-1])

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,W=LI()
m={}
for i in range(n):
    w,v=LI()
    if w in m:
        m[w].append(v)
    else:
        m[w]=[v]

a=[]
for i,j in m.items():
    sj=sorted(j)[::-1]
    aj=[sum(j)]
    for x in sj:
        aj+=[aj[-1]-x]
    a.append([i,len(j),aj])

cnt0=[0]*len(m.items())
weights=[i for i,j,k in a]

ans=0
sys.setrecursionlimit(10**6)

v=set()
def dfs(cnt):
    global ans
    k=sum([cnt[i]*101**i for i in range(len(cnt))])
    if k in v:return
    v.add(k)
    tot=0
    V=0
    for i in range(len(cnt)):
        tot+=cnt[i]*weights[i]
        if cnt[i]>a[i][1] or tot>W:
            return
        V+=a[i][2][0]-a[i][2][cnt[i]]
    ans=max(ans,V)
    for i in range(len(cnt)):
        l=[cnt[j] + (1 if i==j else 0) for j in range(len(cnt))]
        dfs(l)

dfs(cnt0)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7
from collections import defaultdict

def ddprint(x):
  if DBG:
    print(x)

n,ww = inm()
w = []
v = []
for i in range(n):
    www,vvv = inm()
    w.append(www)
    v.append(vvv)
h = [ defaultdict(int) for i in range(n+1) ]
for i in range(n):
    h[i][0] = 0
for i in range(n):
    for u in h[i]:
        h[i+1][u] = max(h[i+1][u], h[i][u])
        if u+w[i] <= ww:
            h[i+1][u+w[i]] = max(h[i+1][u+w[i]], h[i][u]+v[i])
print(max(list(h[n].values())))

Submission status: Accepted

Solution code:
from itertools import accumulate

N, constW = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
W0 = WV[0][0]
L = [[] for _ in range(4)]
for w, v in WV:
  w -= W0
  L[w].append(v)
L[0].sort(reverse=True)
L0 = [0] + list(accumulate(L[0]))
l0 = len(L0) - 1
L[1].sort(reverse=True)
L1 = [0] + list(accumulate(L[1]))
l1 = len(L1) - 1
L[2].sort(reverse=True)
L2 = [0] + list(accumulate(L[2]))
l2 = len(L2) - 1
L[3].sort(reverse=True)
L3 = [0] + list(accumulate(L[3]))
l3 = len(L3) - 1
ans = 0
for i in range(1, constW//W0 + 1):
  rest = constW - i*W0
  for j in range(min(rest//3, i, l3) + 1):
    rest1 = rest - 3*j
    for k in range(min(rest1//2, i-j, l2) + 1):
      rest2 = rest1 - 2*k
      for l in range(min(rest2, i-j-k, l1) + 1):
        temp = L3[j] + L2[k] + L1[l] + L0[min(l0, i-j-k-l)]
        ans = max(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
N, constW = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
W0 = WV[0][0]
L = [[] for _ in range(4)]
for w, v in WV:
  w -= W0
  L[w].append(v)
L[0].sort(reverse=True)
L[1].sort(reverse=True)
L[2].sort(reverse=True)
L[3].sort(reverse=True)
ans = 0
for i in range(1, constW//W0 + 1):
  rest = constW - i*W0
  for j in range(min(rest//3, i) + 1):
    rest1 = rest - 3*j
    for k in range(min(rest1//2, i-j) + 1):
      rest2 = rest1 - 2*k
      for l in range(min(rest2, i-j-k) + 1):
        temp = sum(L[3][:j]) + sum(L[2][:k]) + sum(L[1][:l]) + sum(L[0][:i-j-k-l])
        ans = max(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, W = lr()
WV = [lr() for _ in range(N)]
# 重さの総和は0か w1<total<(w1+3)*100
base = WV[0][0]
W0 = [0] + sorted([v for w, v in WV if w == base + 0], reverse=True)
W1 = [0] + sorted([v for w, v in WV if w == base + 1], reverse=True)
W2 = [0] + sorted([v for w, v in WV if w == base + 2], reverse=True)
W3 = [0] + sorted([v for w, v in WV if w == base + 3], reverse=True)
W0cum = np.array(W0).cumsum()
W1cum = np.array(W1).cumsum()
W2cum = np.array(W2).cumsum()
W3cum = np.array(W3).cumsum()
answer = 0
for a in range(len(W0)):
    for b in range(len(W1)):
        for c in range(len(W2)):
            for d in range(len(W3)):
                remain = W - a * base - b * (base+1) - c * (base+2) - d * (base+3)
                if remain < 0:
                    continue
                answer = max(answer, W0cum[a] + W1cum[b] + W2cum[c] + W3cum[d])

print(answer)

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(n)]
from collections import defaultdict
dp=defaultdict(int)
dp[0]=0
for w,v in items:
  for tw,tv in list(dp.items()):
    if tw+w<=W:
      dp[tw+w]=max(tv+v,dp[tw+w])
print(max(dp.values()))

Submission status: Accepted

Solution code:
INFTY = 10**10
N,W = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
dp = [[[-INFTY for _ in range(3*(N-1)+1)] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    for j in range(1,i+1):
        for k in range(3*(N-1)+1):
            dp[i][j][k] = dp[i-1][j][k]
            if k>=X[i-1][0]-X[0][0]:
                dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-X[i-1][0]+X[0][0]]+X[i-1][1])
cmax = 0
for j in range(1,N+1):
    for k in range(3*(N-1)+1):
        if j*X[0][0]+k<=W:
            cmax = max(cmax,dp[N][j][k])
print(cmax)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
dic = {"0":[],"1":[],"2":[],"3":[]}
for i in range(N):
  w,v = map(int,input().split())
  if i == 0:
    Min = w
  if w == Min:
    dic["0"].append(v)
  elif w == Min+1:
    dic["1"].append(v)
  elif w == Min+2:
    dic["2"].append(v)
  elif w == Min+3:
    dic["3"].append(v)
    
dic["0"].sort(reverse=True)
dic["1"].sort(reverse=True)
dic["2"].sort(reverse=True)
dic["3"].sort(reverse=True)

ans = 0
for i in range(len(dic["0"])+1):
  for j in range(len(dic["1"])+1):
    for k in range(len(dic["2"])+1):
      for l in range(len(dic["3"])+1): 
        a = int(sum(dic["0"][:i])+sum(dic["1"][:j])+sum(dic["2"][:k])+sum(dic["3"][:l])) 
        b = int(i*Min+j*(Min+1)+k*(Min+2)+l*(Min+3))
        if a > ans and b <= W:
          ans = a
print(int(ans))

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
from collections import defaultdict
wvl = defaultdict(list)
for i in range(N):
    w,v = map(int,input().split())
    if i == 0:
        f_w = w
    wvl[w].append(v)

import itertools
for i in range(f_w, f_w+4):
    wvl[i] = [0] + list(itertools.accumulate(sorted(wvl[i], reverse=True)))

ans = 0
for i in range(101):
    if len(wvl[f_w])-1 < i:
        break
    for j in range(101-i):
        if len(wvl[f_w+1])-1 < j:
            break
        for k in range(101-i-j):
            if len(wvl[f_w+2])-1 < k:
                break
            rest = W - f_w * i - (f_w+1) * j - (f_w+2) * k
            l = min(rest // (f_w + 3), len(wvl[f_w+3])-1)
            if l < 0:
                break
            
            ans = max(ans, wvl[f_w][i] + wvl[f_w+1][j] + wvl[f_w+2][k] + wvl[f_w+3][l])
            
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
D = {0: 0}
for i in range(N):
  w, v = map(int, input().split())
  A = [[i, D[i]] for i in D]
  for j in A:
    if j[0] + w <= W:
      if j[0] + w in D:
        D[j[0] + w] = max(D[j[0] + w], j[1] + v)
      else:
        D[j[0]+w] = j[1]+v
print(max(D[i] for i in D))

Submission status: Accepted

Solution code:
from itertools import accumulate
N, W = map(int, input().split())
xs = [[0] for _ in range(4)]
for i in range(1, N+1):
    w, v = map(int, input().split())
    if i == 1:
        cc = w
    xs[w-cc].append(v)
A, B, C, D = map(len, xs)
As, Bs, Cs, Ds = map(lambda x: list(accumulate([0]+sorted(x)[::-1])), xs)

def f(a, b, c, d):
    return As[a] + Bs[b] + Cs[c] + Ds[d]

def main():
    r = 0
    for a in range(A):
        for b in range(B):
            for c in range(C):
                for d in range(D):
                    w = cc*(a+b+c+d)+b+c*2+d*3
                    if w > W:
                        break
                    r = max(f(a,b,c,d), r)
    print(r)

main()

Submission status: Accepted

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

N, W = map(int, input().split())
A = [[] for _ in range(4)]
for i in range(N):
    w, v = map(int, input().split())
    if i == 0: w0 = w
    A[w-w0].append(v)

B = [[0] for _ in range(4)]
for i in range(4):
    A[i].sort(reverse=True)
    b = 0
    for a in A[i]:
        b += a
        B[i].append(b)
#print(B)
ans = 0
for n1, b1 in enumerate(B[0]):
    for n2, b2 in enumerate(B[1]):
        for n3, b3 in enumerate(B[2]):
            n4 = min((W - n1*w0 - n2*(w0+1) - n3*(w0+2)) // (w0+3), len(B[3])-1)
            if n4 < 0: continue
            ans = max(ans, b1+b2+b3+B[3][n4])

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
b = []
for _ in range(N):
  w, v = map(int, input().split())
  b.append((w, v))
wbias = b[0][0]
dp = [[[0] * (3 * N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
for i in range(N):
  for k in range(N):
    for j in range(3 * N + 1):
      if i + 1 <= N:
        dp[i + 1][k][j] = max(dp[i + 1][k][j], dp[i][k][j])
        if j + b[i][0] - wbias <= 3 * N and (k < N):
          dp[i + 1][k + 1][j + b[i][0] - wbias] = max(dp[i + 1][k + 1][j + b[i][0] - wbias], dp[i][k][j] + b[i][1])

#print(dp)
res = 0
for k in range(N + 1):
  for j in range(3 * N + 1):
    if j + k * wbias <= W:
      res = max(res, dp[-1][k][j])
print(res)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
items = [[] for _ in range(4)]
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        w0 = w
        items[0].append(v)
    else:
        items[w-w0].append(v)

items = [[0]+sorted(items[i], reverse=True) for i in range(4)]
for i in range(4):
    for j in range(1, len(items[i])):
        items[i][j] += items[i][j-1]

ans = 0
for i in range(len(items[0])):
    for j in range(len(items[1])):
        for k in range(len(items[2])):
            for l in range(len(items[3])):
                if w0*(sum((i, j, k, l))) + j + k*2+l*3 <= W:
                    ans = max(
                        ans, sum((items[0][i], items[1][j], items[2][k], items[3][l])))

print(ans)

Submission status: Accepted

Solution code:
def solve():
    from itertools import accumulate

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

    e = tuple([] for _ in range(4))
    w1, v1 = map(int, input().split())
    e[0].append(v1)

    for _ in range(N - 1):
        _w, _v = map(int, input().split())
        e[_w - w1].append(_v)

    g = [None for _ in range(4)]
    for j in range(4):
        e[j].sort(reverse=True)
        g[j] = (0,) + tuple(accumulate(e[j]))

    ret = 0
    for a in range(len(e[0]) + 1):
        for b in range(len(e[1]) + 1):
            for c in range(len(e[2]) + 1):
                diff = W - (w1 * a + (w1 + 1) * b + (w1 + 2) * c)
                if diff < 0:
                    break
                d = min(len(e[3]), diff // (w1 + 3))
                ret = max(ret, g[0][a] + g[1][b] + g[2][c] + g[3][d])
    return ret


print(solve())

# https://atcoder.jp/contests/arc073/submissions/2794675
# https://atcoder.jp/contests/arc073/submissions/7328854

Submission status: Accepted

Solution code:
def solve():
    from itertools import accumulate

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

    e = tuple([] for _ in range(4))
    w1, v1 = map(int, input().split())
    e[0].append(v1)

    for _ in range(N - 1):
        _w, _v = map(int, input().split())
        e[_w - w1].append(_v)

    g = [None for _ in range(4)]
    for j in range(4):
        e[j].sort(reverse=True)
        g[j] = (0,) + tuple(accumulate(e[j]))

    ret = 0
    for a in range(min(len(e[0]), N) + 1):
        for b in range(min(len(e[1]), N - a) + 1):
            for c in range(min(len(e[2]), N - a - b) + 1):
                diff = W - (w1 * a + (w1 + 1) * b + (w1 + 2) * c)
                if diff < 0:
                    break
                d = min(len(e[3]), diff // (w1 + 3))
                ret = max(ret, g[0][a] + g[1][b] + g[2][c] + g[3][d])
    return ret


print(solve())

# https://atcoder.jp/contests/arc073/submissions/2794675

Submission status: Accepted

Solution code:
def solve():
    from itertools import accumulate

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

    e = tuple([] for _ in range(4))
    w1, v1 = map(int, input().split())
    e[0].append(v1)

    for _ in range(N - 1):
        _w, _v = map(int, input().split())
        e[_w - w1].append(_v)

    g = [None for _ in range(4)]
    for j in range(4):
        e[j].sort(reverse=True)
        g[j] = (0,) + tuple(accumulate(e[j]))

    ret = 0
    for a in range(min(len(e[0]), N) + 1):
        for b in range(min(len(e[1]), N - a) + 1):
            for c in range(min(len(e[2]), N - a - b) + 1):
                for d in range(min(len(e[3]), N - a - b - c) + 1):
                    if w1 * a + (w1 + 1) * b + (w1 + 2) * c + (w1 + 3) * d > W:
                        break
                    ret = max(ret, g[0][a] + g[1][b] + g[2][c] + g[3][d])
    return ret


print(solve())

Submission status: Accepted

Solution code:
import bisect
N,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(N)]
w1=wv[0][0]

Wlist=[0]+[j*w1+i for j in range(1,N+1) for i in range(3*j+1)]
Wlist=sorted(set(Wlist))
LW=len(Wlist)
dp=[[0]*LW for _ in range(N+1)]
#dp[i][j]:N個の物に対して強度(Wlist[j])のバッグ

for i in range(1,N+1):
  w,v=wv[i-1]
  for j in range(LW):
    if w<=Wlist[j]:      
      ind=bisect.bisect_right(Wlist,Wlist[j]-w)-1
      dp[i][j]=max(dp[i-1][j],dp[i-1][ind]+v)
    else:
      dp[i][j]=dp[i-1][j]

ind=bisect.bisect_right(Wlist,W)-1
print(dp[N][ind])

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product, accumulate

N, W = map(int, input().split())
items = defaultdict(list)
for _ in range(N):
    w, v = map(int, input().split())
    items[w].append(v)
weights = list(items.keys())
nums = {w: len(items[w]) for w in weights}
cumsum = {w: None for w in weights}
for i, w in enumerate(weights):
    items[w].sort(reverse=True)
    cumsum[w] = [0] + list(accumulate(items[w]))
ans = 0
for tup in product(*[range(nums[w] + 1) for w in weights]):
    temp_weight = sum(w * t for w, t in zip(weights, tup))
    if temp_weight > W: continue
    temp_value = sum(cumsum[w][t] for w, t in zip(weights, tup))
    ans = max(temp_value, ans)
print(ans)

Submission status: Accepted

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

dp_list = [ [ None for i in range(4*n+1) ] for i in range(n+1) ]
dp_list[0][0] = 0
base = knapsack[0][0]


for wi, vi in knapsack:
    wi -= base
    for i in range(n-1,-1,-1):
        for j in range(4*n,-1,-1):
            if 0 <= j-wi < 4*n+1 and 0 <= j < 4*n+1:
                if dp_list[i][j-wi] is not None:
                    if dp_list[i+1][j] is None:
                        dp_list[i+1][j] = dp_list[i][j-wi] + vi
                    else:
                        dp_list[i+1][j] = max(dp_list[i][j-wi] + vi, dp_list[i+1][j])

ans_list = [0]
for i in range(1,n+1):
    l = w - i*base
    for j in range(min(4*n+1,l+1)):
        if dp_list[i][j] is not None:
            ans_list.append(dp_list[i][j])


print(max(ans_list))

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, W = getlist()
	stock = []
	for i in range(N):
		w, v = getlist()
		stock.append([w, v])
	w1 = stock[0][0]
	for i in range(N):
		stock[i][0] -= w1

	DP = [[[-INF] * (N + 1) for i in range(3 * N + 1)] for j in range(N + 1)]
	DP[0][0][0] = 0
	#DP
	for i in range(N):
		for j in range(3 * N):
			for k in range(N):
				if DP[i][j][k] != -INF:
					DP[i + 1][j + stock[i][0]][k + 1] = max(DP[i + 1][j + stock[i][0]][k + 1], DP[i][j][k] + stock[i][1])
					DP[i + 1][j][k] = max(DP[i + 1][j][k], DP[i][j][k])

	#答え
	ans = 0
	for i in range(3 * N + 1):
		for j in range(N + 1):
			if DP[N][i][j] != INF and i + j * w1 <= W:
				ans = max(ans, DP[N][i][j])
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    N, W = map(int, input().split())
    d = defaultdict(list)
    w1 = 0
    for i in range(N):
        w, v = map(int, input().split())
        if i == 0:
            w1 = w
        d[w].append(v)

    ans = 0
    d[w1].sort(reverse=True)
    d[w1 + 1].sort(reverse=True)
    d[w1 + 2].sort(reverse=True)
    d[w1 + 3].sort(reverse=True)

    for i in range(len(d[w1])+1):
        for j in range(len(d[w1+1])+1):
            for k in range(len(d[w1+2])+1):
                for l in range(len(d[w1+3])+1):
                    tmp = sum(d[w1][:i]) + sum(d[w1+1][:j]) + sum(d[w1+2][:k]) + sum(d[w1+3][:l])

                    if w1 * i + (w1+1) * j + (w1+2) * k + (w1+3) * l <= W:
                        ans = max(ans,tmp)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

n, wmax = map(int, input().split())
dp = [defaultdict(int) for _ in range(2)]
dp[0][0] = 0
for i in range(n):
    w, v = map(int, input().split())
    if i == 0:
        w0 = w
    dp[(i+1)%2] = defaultdict(int)
    for j in range(n+1):
        for k in range(300):
            weight = j*w0+k
            if weight <= wmax:
                if weight - w >= 0:
                    dp[(i+1)%2][weight] = max(dp[(i+1)%2][weight], dp[i%2][weight - w] + v)
                dp[(i+1)%2][weight] = max(dp[(i+1)%2][weight], dp[i%2][weight])

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