Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

1 ≤ N ≤ 100

1 ≤ W ≤ 10^9

1 ≤ w_i ≤ 10^9

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

1 ≤ v_i ≤ 10^7

W, each w_i and v_i are integers.

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible total value of the selected items.

Sample Input 1

4 6
2 1
3 4
4 10
3 4

Sample Output 1

11

The first and third items should be selected.

Sample Input 2

4 6
2 1
3 7
4 10
3 6

Sample Output 2

13

The second and fourth items should be selected.

Sample Input 3

4 10
1 100
1 100
1 100
1 100

Sample Output 3

400

You can take everything.

Sample Input 4

4 1
10 100
10 100
10 100
10 100

Sample Output 4

0

You can take nothing.



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


Sample output:
11

Submission status: Accepted

Solution code:
from collections import defaultdict

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

MAX_NUM = []
len_weights = 0
def dfs(nums):
    if len(nums) == len_weights:
        sum_w = 0
        value = 0
        for i in range(len_weights):
            sum_w += weights[i] * nums[i]
            if nums[i] >= 1:
                value += items[weights[i]][nums[i] - 1]
        return value if sum_w <= W else 0
    value = 0
    i = len(nums)
    for j in range(MAX_NUM[i] + 1):
        value = max(value, dfs(nums + [j]))
    return value

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

for v in items.values():
    v.sort(reverse=True)
    for i in range(1, len(v)):
        v[i] = v[i - 1] + v[i]

weights = sorted(items.keys())
len_weights = len(weights)
for w in weights:
    MAX_NUM.append(min(W // w, len(items[w])))
print(dfs([]))

Submission status: Accepted

Solution code:
from collections import *

N,W=map(int,input().split())
d=defaultdict(int)
d[0]=0
for i in range(N):
    w,v=map(int,input().split())
    for p,q in d.copy().items():
        if p+w<=W:
            d[p+w]=max(d[p+w],q+v)
print(max(d.values()))

Submission status: Accepted

Solution code:
from collections import *

N,W=map(int,input().split())
d=defaultdict(int)
d[0]=0
for i in range(N):
    w,v=map(int,input().split())
    c=d.copy()
    for p,q in c.items():
        if p+w<=W:
            d[p+w]=max(d[p+w],q+v)
print(max(d.values()))

Submission status: Accepted

Solution code:
from itertools import accumulate
n, W = [int(item) for item in input().split()]
wv = [[] for _ in range(4)]
for i in range(n):
    w, v = [int(item) for item in input().split()]
    if i == 0:
        w1 = w
    wv[w-w1].append(v)
for i in range(4):
    wv[i] = sorted(wv[i], reverse=True)
    wv[i] = [0] + list(accumulate(wv[i]))

ans = 0
for i in range(len(wv[0])):
    for j in range(len(wv[1])):
        for k in range(len(wv[2])):
            for l in range(len(wv[3])):
                if j*1 + k*2 + l*3 <= W - w1*(i+j+k+l):
                    ans = max(ans, wv[0][i] + wv[1][j] + wv[2][k] + wv[3][l])
print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
    n,w = [int(i) for i in input().split()]
    vals = [[], [], [], []]

    w0, v0 = [int(i) for i in input().split()]
    vals[0].append(v0)

    for i in range(n - 1):
        wi, vi = [int(i) for i in input().split()]
        vals[wi-w0].append(vi)

    vals[0].sort(reverse=True)
    vals[1].sort(reverse=True)
    vals[2].sort(reverse=True)
    vals[3].sort(reverse=True)

    ans = 0
    for i, j, k, l in itertools.product(range(len(vals[0])+1), range(len(vals[1])+1), range(len(vals[2])+1), range(len(vals[3])+1)):
        if i * w0 + j * (w0 + 1) + k * (w0 + 2) + l * (w0 + 3) <= w:
            ans = max(ans, sum(vals[0][:i]) + sum(vals[1][:j]) + sum(vals[2][:k]) + sum(vals[3][:l]))

    print(ans)

main()

Submission status: Accepted

Solution code:
# Editorial

import sys
from itertools import accumulate

def main():
    input = sys.stdin.readline
    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)

    for i in range(4):
        V[i] = list(accumulate([0] + sorted(V[i], key=lambda x: -x)))

    ans = 0
    for i in range(len(V[0])):
        for j in range(len(V[1])):
            for k in range(len(V[2])):
                weight = w0 * i + (w0 + 1) * j + (w0 + 2) * k
                if weight <= W:
                    l  = min(len(V[3]) - 1, (W - weight) // (w0 + 3))
                    ans = max(ans, V[0][i] + V[1][j] + V[2][k] + V[3][l])

    return ans


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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque

def main():
    input = sys.stdin.readline
    N, W = map(int, input().split())
    A = [tuple(map(int, input().split())) for _ in range(N)]

    d = defaultdict(lambda: 0)
    q = deque()
    for a in A:
        while len(q) > 0:
            w0, v0 = q.popleft()

            w1 = w0 + a[0]
            v1 = v0 + a[1]

            if w1 <= W:
                d[w1] = max(d[w1], v1)

            d[w0] = max(d[w0], v0)

        if a[0] <= W:
            q.append(a)

        for key in d.keys():
            q.append((key, d[key]))

    ans = 0
    for key in d.keys():
        ans = max(ans, d[key])

    return ans


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

Submission status: Accepted

Solution code:
from collections import defaultdict as d
s=d(int)
s[0]=0
n,w=map(int,input().split())
for i in range(n):
    q,v=map(int,input().split())
    c=s.copy()
    for p,r in c.items():
        if p+q<=w:
            s[p+q]=max(s[p+q],r+v)
print(max(s.values()))

Submission status: Accepted

Solution code:
def simple_knapsack(N: int, W: int, items: list) -> int:
    w0 = items[0][0]
    d = {w0+i: [] for i in range(4)}
    for w, v in items:
        d[w].append(v)

    s = {}
    for k, values in d.items():
        s[k] = [0] * (len(values)+1)
        for i, v in enumerate(sorted(values, key=lambda x: -x)):
            s[k][i + 1] = s[k][i] + v

    w0, w1, w2, w3 = w0, w0 + 1, w0 + 2, w0 + 3

    max_value = 0
    for i1 in range(len(s[w0])):
        if W < w0 * i1:
            break
        for i2 in range(len(s[w1])):
            if W < w0 * i1 + w1 * i2:
                break
            for i3 in range(len(s[w2])):
                if W < w0 * i1 + w1 * i2 + w2 * i3:
                    break
                for i4 in range(len(s[w3])):
                    if W < w0 * i1 + w1 * i2 + w2 * i3 + w3 * i4:
                        break
                    max_value = max(
                        max_value, s[w0][i1] + s[w1][i2] + s[w2][i3] + s[w3][i4])

    return max_value


if __name__ == "__main__":
    N = 0
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    ans = simple_knapsack(N, W, items)
    print(ans)

Submission status: Accepted

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

N,W = map(int,input().split())
info = []
for i in range(N):
    w,v = map(int,input().split())
    if i == 0:
        w1 = w
    w = w - (w1-1)
    info.append((w,v))
# dp[i][j][k]
# dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-w][k-1])
# dp[0][j][0] = 0
# ans = max(dp[N][j][k] w1*k + j <= W)
dp = [[[0]*(N+1) for _ in range(400)] for _ in range(N+1)]
for i in range(1,N+1):
    w = info[i-1][0]; v = info[i-1][1]
    for j in range(400):
        for k in range(1,N+1):
            dp[i][j][k] = dp[i-1][j][k]
            if j - w >= 0:
                if dp[i][j][k] < dp[i-1][j-w][k-1] + v:
                    dp[i][j][k] = dp[i-1][j-w][k-1] + v
ans = -1
for j in range(400):
    for k in range(N+1):
        if not((w1-1)*k + j <= W):
            continue
        if dp[N][j][k] > ans:
            ans = dp[N][j][k]
print(ans)

Submission status: Accepted

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

dp = {}
dp[0] = 0
for w, v in a:
    pre_dp = dp.copy()
    for pw, pv in pre_dp.items():
        if pw + w <= W:
            dp[pw + w] = max(dp.get(pw + w, 0), pv + v)

print(max(dp.values()))

Submission status: Accepted

Solution code:
n,W = map(int,input().split())
a = {}
for i in range(n):
    w,v = map(int,input().split())
    a.setdefault(w, []).append(v)

we = [0]*4
va = []
num = [0]*4
for i,[k,v] in enumerate(a.items()):
    we[i] = k
    va.append(sorted(v,reverse=True))
    num[i] = len(v)
for i in range(4-len(va)):
    va.append([0])

ans = -float('inf')
for i in range(max(1,num[0]+1)):
    for j in range(max(1,num[1]+1)):
        for k in range(max(1,num[2]+1)):
            for l in range(max(1,num[3]+1)):
                if we[0]*i + we[1]*j + we[2]*k + we[3]*l <= W:
                    total = 0
                    for im,m in enumerate([i,j,k,l]):
                        total += sum(va[im][:m])
                    ans = max(ans, total)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,W=map(int,input().split())
w1,v1=map(int,input().split())
V=[[v1],[],[],[]]
for i in range(N-1):
    w,v=map(int,input().split())
    V[w-w1].append(v)
for i in range(4):
    V[i].sort(reverse=True)
W0=W
V0=0
ans=0
for a in range(-1,len(V[0])):
    if a!=-1:
        W0-=w1
        if W0<0:
            break
        V0+=V[0][a]
    W1=W0
    V1=V0
    ans=max(ans,V0)
    for b in range(-1,len(V[1])):
        if b!=-1:
            W1-=w1+1
            if W1<0:
                break
            V1+=V[1][b]
        W2=W1
        V2=V1
        ans=max(ans,V1)
        for c in range(-1,len(V[2])):
            if c!=-1:
                W2-=w1+2
                if W2<0:
                    break
                V2+=V[2][c]
            ans=max(ans,V2)
            if W2//(w1+3)>0:
                ans=max(ans,V2+sum(V[3][0:(W2//(w1+3))]))
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    dp = {0: 0}
    for i in range(N):
        w, v = map(int, input().split())
        nxt = {}
        for k in dp:
            if k+w <= W:
                nxt[k+w] = max(dp[k] + v, dp[k+w] if k+w in dp else 0)
        dp.update(nxt)
    ans = 0
    for k in dp:
        ans = max(ans, dp[k])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, max_w = map(int, input().split())
item = [tuple(int(x) for x in input().split()) for _ in range(n)]

ans = dict()
ans[0] = 0
for w, v in item:
    next = dict()
    for temp_w, temp_v in ans.items():
        if temp_w + w <= max_w:
            if temp_w + w not in next.keys():
                next[temp_w + w] = temp_v + v
            else:
                if temp_v + v > next[temp_w + w]:
                    next[temp_w + w] = temp_v + v
    #print(next)
    for x, y in next.items():
        if x not in ans.keys():
            ans[x] = y
        else:
            if y > ans[x]:
                ans[x] = y

#print(ans)
res = 0
for x, y in ans.items():
    res = max(res, y)

print(res)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
""""
n,T = LI()
ans = 0
t = LI()
for i in range(n-1):
    ans += min(T,t[i+1]-t[i])
ans += T
print(ans)
"""

#D
n,w = LI()
g = LIR(n)
l = [[] for i in range(4)]
for W,v in g:
    l[W-g[0][0]].append(v)
    l[W-g[0][0]].sort(reverse = True)
l0 = len(l[0])
l1 = len(l[1])
l2 = len(l[2])
l3 = len(l[3])
for i in range(l0-1):
    l[0][i+1] += l[0][i]
l[0].insert(0,0)
for i in range(l1-1):
    l[1][i+1] += l[1][i]
l[1].insert(0,0)
for i in range(l2-1):
    l[2][i+1] += l[2][i]
l[2].insert(0,0)
for i in range(l3-1):
    l[3][i+1] += l[3][i]
l[3].insert(0,0)
ans = 0
for i in range(l0+1):
    for j in range(l1+1):
        for k in range(l2+1):
            for m in range(l3+1):
                if i*g[0][0]+j*(g[0][0]+1)+k*(g[0][0]+2)+m*(g[0][0]+3) <= w:
                    ans = max(ans,l[0][i]+l[1][j]+l[2][k]+l[3][m])
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
L = []
for i in range(N):
  L.append(list(map(int,input().split())))
Vmax = 0
w_1 = []
w_2 = []
w_3 = []
w_4 = []
for i in range(N):
  if L[i][0] == L[0][0]:
    w_1.append(L[i][1])
  elif L[i][0] == L[0][0]+1:
    w_2.append(L[i][1])
  elif L[i][0] == L[0][0]+2:
    w_3.append(L[i][1])
  else:
    w_4.append(L[i][1])
w_1.sort()
w_2.sort()
w_3.sort()
w_4.sort()
w_1.reverse()
w_2.reverse()
w_3.reverse()
w_4.reverse()
for i in range(1,len(w_1)):
  w_1[i] = w_1[i-1]+w_1[i]
for i in range(1,len(w_2)):
  w_2[i] = w_2[i-1]+w_2[i]
for i in range(1,len(w_3)):
  w_3[i] = w_3[i-1]+w_3[i]
for i in range(1,len(w_4)):
  w_4[i] = w_4[i-1]+w_4[i]
w_1.append(0)
w_2.append(0)
w_3.append(0)
w_4.append(0)
for j in range(len(w_1)):
  for k in range(len(w_2)):
    for l in range(len(w_3)):
      for m in range(len(w_4)):
        if j*L[0][0]+k*(L[0][0]+1)+l*(L[0][0]+2)+m*(L[0][0]+3) > W:
          continue
        else:
          if w_1[j-1]+w_2[k-1]+w_3[l-1]+w_4[m-1] >= Vmax:
            Vmax = w_1[j-1]+w_2[k-1]+w_3[l-1]+w_4[m-1]
print(Vmax)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,W = map(int, input().split())
wv = [list(map(int,input().split())) for _ in range(N)]

dp = defaultdict(int)
dp[0] = 0
for w, v in wv:
    dp_cur = list(dp.items())
    for w_cur, v_cur in dp_cur:
        if w_cur+w <= W:
            dp[w_cur+w] = max(dp[w_cur+w],v_cur+v)

print(max(dp.values()))

Submission status: Accepted

Solution code:
n,max_w = map(int,input().split())
w1=[]
w2=[]
w3=[]
w4=[]
v1=[]
v2=[]
v3=[]
v4=[]

w_1,v_1 = map(int,input().split())
w1.append(w_1)
v1.append(v_1)

for i in range(1,n):
  tmp_w,tmp_v = map(int,input().split())
  if tmp_w == w_1:
    w1.append(tmp_w)
    v1.append(tmp_v)
  elif tmp_w == w_1+1:
    w2.append(tmp_w)
    v2.append(tmp_v)
  elif tmp_w == w_1+2:
    w3.append(tmp_w)
    v3.append(tmp_v)
  elif tmp_w == w_1+3:
    w4.append(tmp_w)
    v4.append(tmp_v)
  

count1 = len(w1)
count2 = len(w2)
count3 = len(w3)
count4 = len(w4)

v1 = sorted(v1,reverse=True)
v2 = sorted(v2,reverse=True)
v3 = sorted(v3,reverse=True)
v4 = sorted(v4,reverse=True)

ruiseki_v1 = [0]*count1
ruiseki_v2 = [0]*count2
ruiseki_v3 = [0]*count3
ruiseki_v4 = [0]*count4

if v1:
  ruiseki_v1[0]=v1[0]
  for i in range(count1-1):
    ruiseki_v1[i+1]=ruiseki_v1[i]+v1[i+1]

if v2:
  ruiseki_v2[0]=v2[0]
  for i in range(count2-1):
    ruiseki_v2[i+1]=ruiseki_v2[i]+v2[i+1]

if v3:
  ruiseki_v3[0]=v3[0]
  for i in range(count3-1):
    ruiseki_v3[i+1]=ruiseki_v3[i]+v3[i+1]

if v4:
  ruiseki_v4[0]=v4[0]
  for i in range(count4-1):
    ruiseki_v4[i+1]=ruiseki_v4[i]+v4[i+1]

ruiseki_v1.insert(0,0)
ruiseki_v2.insert(0,0)
ruiseki_v3.insert(0,0)
ruiseki_v4.insert(0,0)

ans = 0 
for i in range(count1+1):
  for j in range(count2+1):
    for k in range(count3+1):
      for l in range(count4+1):
        if i*w_1 + j*(w_1+1) + k*(w_1+2) +l*(w_1+3) <= max_w:
          ans = max(ans,ruiseki_v1[i]+ruiseki_v2[j]+ruiseki_v3[k]+ruiseki_v4[l])
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import namedtuple


def next_str() -> str:
    result = ""
    while True:
        tmp = sys.stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


def next_int() -> int:
    return int(next_str())


item = namedtuple("itm", ("w", "v"))
n, W = map(int, input().split())
items = [item(next_int(), next_int()) for i in range(n)]
dic = dict()


def rec_dp(i: int, w: int) -> int:
    if (i, w) in dic:
        return dic[(i, w)]

    result = 0
    if i == n:
        pass
    elif w - items[i].w < 0:
        result = rec_dp(i + 1, w)
    else:
        result = max(
            rec_dp(i + 1, w),
            rec_dp(i + 1, w - items[i].w) + items[i].v
        )
    dic[(i, w)] = result
    return result


def main() -> None:
    print(rec_dp(0, W))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

for i in d.keys():
    d[i].sort(reverse=True)
    *d[i],=accumulate([0]+d[i])

ans=0
i,j,k,l=d.keys()
for ai,bi in enumerate(d[i]):
    for aj,bj in enumerate(d[j]):
        for ak,bk in enumerate(d[k]):
            for al,bl in enumerate(d[l]):
                if i*ai+j*aj+k*ak+l*al<=W:
                    ans=max(ans,bi+bj+bk+bl)

print(ans)

Submission status: Accepted

Solution code:
def func(n, W, w):  # ナップザック問題の亜種
    _max = 0
    weights = [[] for _ in range(4)]
    for i in range(n):
        weights[w[i][0]-w[0][0]].append(w[i][1])
    for i in range(len(weights)):
        weights[i].sort()
        weights[i].append(0)
        weights[i].reverse()
        for j in range(1, len(weights[i])):
            weights[i][j] += weights[i][j-1]
    # print(weights)
    for i in range(len(weights[0])):
        # print("i:{}".format(i))
        for j in range(len(weights[1])):
            # print("j:{}".format(j))
            for k in range(len(weights[2])):
                for l in range(len(weights[3])):
                    # 「i+j+k+l < n」つ選ぶ
                    if w[0][0]*i\
                            + (w[0][0]+1)*j\
                            + (w[0][0]+2)*k\
                            + (w[0][0]+3)*l <= W:
                        # print("i:{} j:{} k:{} l:{} score:{}".format(i, j, k, l, weights[0][i]+weights[1][
                        # j]+weights[2][k]+weights[3][l]))
                        _max = max(_max, weights[0][i]+weights[1][j]+weights[2][k]+weights[3][l])
    return _max


n, W = [int(i) for i in input().split()]
w = [[0, 0] for _ in range(n)]
for i in range(n):
    w[i] = [int(i) for i in input().split()]
print(func(n, W, w))
"""
# print("print(\" vs \" + str(func({}, {}, {})))".format(n, W, w))
print("11 vs " + str(func(4, 6, [[2, 1], [3, 4], [4, 10], [3, 4]])))
print("13 vs " + str(func(4, 6, [[2, 1], [3, 7], [4, 10], [3, 6]])))
print("400 vs " + str(func(4, 10, [[1, 100], [1, 100], [1, 100], [1, 100]])))
print("0 vs " + str(func(4, 1, [[10, 100], [10, 100], [10, 100], [10, 100]])))
"""

Submission status: Accepted

Solution code:
def solve(N, W, WVs):
    Ws = {}
    for w, v in WVs:
        Ws.setdefault(w, []).append(v)
    for w, v in Ws.items():
        Ws[w] = sorted(v, key=lambda x: -x)
    wkeys = sorted(Ws.keys())

    m = 0
    for n1 in range(N + 1):
        w1 = n1 * wkeys[0]
        if w1 > W:
            break
        v1 = sum(Ws[wkeys[0]][:n1])
        for n2 in range(N - n1 + 1):
            if len(wkeys) >= 2:
                w2 = n2 * wkeys[1]
                if w1 + w2 > W:
                    break
                v2 = sum(Ws[wkeys[1]][:n2])
            else:
                w2, v2 = 0, 0
            for n3 in range(N - n1 - n2 + 1):
                if len(wkeys) >= 3:
                    w3 = n3 * wkeys[2]
                    if w1 + w2 + w3 > W:
                        break
                    v3 = sum(Ws[wkeys[2]][:n3])
                else:
                    w3, v3 = 0, 0
                for n4 in range(N - n1 - n2 - n3 + 1):
                    if len(wkeys) >= 4:
                        w4 = n4 * wkeys[3]
                        if w1 + w2 + w3 + w4 > W:
                            break
                        v4 = sum(Ws[wkeys[3]][:n4])
                    else:
                        w4, v4 = 0, 0

                    m = max(m, v1 + v2 + v3 + v4)

    return m

if __name__ == "__main__":
    N, W = map(int, input().split(" "))
    WVs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, W, WVs))

Submission status: Accepted

Solution code:
from operator import itemgetter
import bisect
from itertools import accumulate
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
WV.sort(key=itemgetter(0, 1))
w, v = zip(*WV)
w0 = w[0]
w1 = w0 + 1
w2 = w1 + 1
w3 = w2 + 1
i0 = bisect.bisect_left(w, w0)
i1 = bisect.bisect_left(w, w1)
i2 = bisect.bisect_left(w, w2)
i3 = bisect.bisect_left(w, w3)
v0 = sorted(v[i0:i1], reverse=True)
v1 = sorted(v[i1:i2], reverse=True)
v2 = sorted(v[i2:i3], reverse=True)
v3 = sorted(v[i3:], reverse=True)
a0 = list(accumulate(v0)) + [0]
a1 = list(accumulate(v1)) + [0]
a2 = list(accumulate(v2)) + [0]
a3 = list(accumulate(v3)) + [0]
n0 = 1 + len(v0)
n1 = 1 + len(v1)
n2 = 1 + len(v2)
n3 = 1 + len(v3)

ans = 0
for i0 in range(n0):
    for i1 in range(n1):
        for i2 in range(n2):
            for i3 in range(n3):
                if i0*w0 + i1*w1 + i2*w2 + i3*w3 <= W:
                    ans = max(ans, a0[i0-1]+a1[i1-1]+a2[i2-1]+a3[i3-1])
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://atcoder.jp/contests/abc060/submissions/3958560
・前から普通にDPもdictでやってみる。
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from collections import defaultdict

N, W = map(int, input().split())
wN = [0] * N
vN = [0] * N
for i in range(N):
    wN[i], vN[i] = map(int, input().split())

# 重さの添字にはdictを使う
dp = [defaultdict(int) for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for k, v in dp[i].items():
        # 重さの条件がOKなら、今回の値を足したケースを次のステップに送る
        if k + wN[i] <= W:
            dp[i+1][k+wN[i]] = max(dp[i][k] + vN[i], dp[i+1][k+wN[i]])
        # 足さないケースを送る
        dp[i+1][k] = max(dp[i][k], dp[i+1][k])

# 最適が重さWを全て使った場合とは限らないのでNステップ目のmaxを取る
print(max(dp[N].values()))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/arc073/editorial.pdf
　　　https://ei1333.hateblo.jp/entry/2017/05/01/004235
　　　https://atcoder.jp/contests/abc060/submissions/3782609
・公式解
・累積和あり
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from collections import defaultdict

N, W = map(int, input().split())
wN = [0] * N
vN = [[] for i in range(4)]
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        offset = w
    vN[w-offset].append(v)

# 重さ毎のリストを降順ソート
for i in range(4):
    # 空リストのままだとこの後ループを回ってくれないので、[0]を追加する
    vN[i] = [0] + sorted(vN[i], reverse=True)

# 累積和
for i in range(4):
    for j in range(1, len(vN[i])):
        vN[i][j] = vN[i][j-1] + vN[i][j]

ans = 0
for i in range(len(vN[0])):
    for j in range(len(vN[1])):
        for k in range(len(vN[2])):
            for l in range(len(vN[3])):
                # 重さリミットを超えるパターンは対象外
                if offset * i + (offset+1) * j + (offset+2) * k + (offset+3) * l > W:
                    continue
                ans = max(vN[0][i] + vN[1][j] + vN[2][k] + vN[3][l], ans)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/arc073/editorial.pdf
　　　https://ei1333.hateblo.jp/entry/2017/05/01/004235
　　　https://atcoder.jp/contests/abc060/submissions/3782609
・公式解
・とりあえず累積和なしでやってみる。
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

N, W = map(int, input().split())
wN = [0] * N
vN = [[] for i in range(4)]
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        offset = w
    vN[w-offset].append(v)

# 重さ毎のリストを降順ソート
for i in range(4):
    # 空リストのままだとこの後ループを回ってくれないので、[0]を追加する
    vN[i] = [0] + sorted(vN[i], reverse=True)

ans = 0
for i in range(len(vN[0])):
    for j in range(len(vN[1])):
        for k in range(len(vN[2])):
            for l in range(len(vN[3])):
                # 重さリミットを超えるパターンは対象外
                if offset * i + (offset+1) * j + (offset+2) * k + (offset+3) * l > W:
                    continue
                ans = max(sum(vN[0][:i+1]) + sum(vN[1][:j+1]) + sum(vN[2][:k+1])+ sum(vN[3][:l+1]), ans)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
・メモ化再帰
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from collections import defaultdict

N, W = map(int, input().split())
wN = [0] * N
vN = [0] * N
for i in range(N):
    wN[i], vN[i] = map(int, input().split())

# memo[i][j]: i番目以降の品物から重さの和がj以下なるように選んだときの価値の和の最大値
memo = [defaultdict(lambda: -1) for i in range(N+1)]

def dfs(cur, wei):
    # 既に調べた場所はそのまま返却
    if memo[cur][wei] != -1:
        return memo[cur][wei]
    # 品物を最後まで見た
    if cur == N:
        res = 0
    # まだ余力があるから両方試す
    elif wei >= wN[cur]:
        res = max(dfs(cur+1, wei-wN[cur]) + vN[cur], dfs(cur+1, wei))
    # もうこの回の荷物は入らない
    else:
        res = dfs(cur+1, wei)
    # ここまでのベストな値をメモに記録してから返却
    memo[cur][wei] = res
    return res
# 0番目以降で容量W以下の場合の結果を表示
print(dfs(0, W))

Submission status: Accepted

Solution code:
from itertools import accumulate

N, W = map(int, input().split())
items = []
for i in range(N):
    items.append(tuple(map(int, input().split())))

w_max = items[0][0] + 3
w0 = items[0][0]
w0_list = []
w1_list = []
w2_list = []
w3_list = []
for item in items:
    w, v = item
    if w == w0:
        w0_list.append(v)
    if w == w0 + 1:
        w1_list.append(v)
    if w == w0 + 2:
        w2_list.append(v)
    if w == w0 + 3:
        w3_list.append(v)
w0_list = sorted(w0_list, reverse=True)
w1_list = sorted(w1_list, reverse=True)
w2_list = sorted(w2_list, reverse=True)
w3_list = sorted(w3_list, reverse=True)

w0_accum = tuple(accumulate(w0_list))
w1_accum = tuple(accumulate(w1_list))
w2_accum = tuple(accumulate(w2_list))
w3_accum = tuple(accumulate(w3_list))

ans = 0
for i in range(len(w0_list)+1):
    for j in range(len(w1_list)+1):
        for k in range(len(w2_list)+1):
            for m in range(len(w3_list)+1):
                if w0 * i + (w0 + 1) * j + (w0 + 2) * k + (w0 + 3) * m > W:
                    continue
                else:
                    tmp = 0
                    if i > 0:
                        tmp += w0_accum[i-1]
                    if j > 0:
                        tmp += w1_accum[j-1]
                    if k > 0:
                        tmp += w2_accum[k-1]
                    if m > 0:
                        tmp += w3_accum[m-1]
                    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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

# 降順ソート
for i in range(4):
    V[i].sort(reverse=True)

# 累積和
S = [[] for _ in range(4)]
for i in range(4):
    S[i] = [0] + list(accumulate(V[i]))

# 全探索
ans = 0
for i0 in range(len(S[0])):
    for i1 in range(len(S[1])):
        for i2 in range(len(S[2])):
            for i3 in range(len(S[3])):
                if w0*i0 + (w0+1)*i1 + (w0+2)*i2 + (w0+3)*i3 <= W:
                    ans = max(ans, S[0][i0]+S[1][i1]+S[2][i2]+S[3][i3])

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, W_limit = map(int, input().split())
W, V = [], []
for i in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

# 基準となるW
base_W = W[0]
# 0 ~ 3の範囲に調節
W = [w - base_W for w in W]

# 重みごとに商品を分ける
Items = [[] for i in range(4)]
for w, v in zip(W, V):
    Items[w].append(v)

# 降順ソートして累積和を取っておく
Items = [[0] + sorted(x, reverse=True) for x in Items]
Items = [list(accumulate(x)) for x in Items]

# それぞれの重さから何個選ぶかで全探索
ans = 0
for w0 in range(len(Items[0])):
    for w1 in range(len(Items[1])):
        for w2 in range(len(Items[2])):
            for w3 in range(len(Items[3])):
                tmp_W = (w0 * base_W) + (w1 * (base_W + 1)) + (w2 * (base_W + 2)) + (w3 * (base_W + 3))
                if tmp_W > W_limit:
                    continue
                tmp_V = Items[0][w0] + Items[1][w1] + Items[2][w2] + Items[3][w3]
                ans = max(ans, tmp_V)

print(ans)

Submission status: Accepted

Solution code:
N, W = [int(_) for _ in input().split()]
WV = [[int(_) for _ in input().split()] for _ in range(N)]
dp = {}
dp[0] = 0
for weight, value in WV:
    dp_old = dp.copy()
    for k, v in dp_old.items():
        if k + weight <= W:
            dp[k + weight] = max(dp.get(k + weight, 0), v + value)
ans = 0
for k, v in dp.items():
    ans = max(ans, v)
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wlist = [0] * N
vlist = [0] * N
for i in range(N):
	wlist[i], vlist[i] = map(int, input().split())
minw = min(wlist)
w = list()
for i in range(4):
	w.append(list())
for i in range(N):
	w[wlist[i] - minw].append(vlist[i])
for i in range(4):
	w[i].sort(reverse = True)
ans = 0
sumw0 = 0
sumv0 = 0
for i in range(len(w[0]) + 1):
	sumw1 = 0
	sumv1 = 0
	for j in range(len(w[1]) + 1):
		sumw2 = 0
		sumv2 = 0
		for k in range(len(w[2]) + 1):
			sumw3 = 0
			sumv3 = 0
			for l in range(len(w[3]) + 1):
				sumw = sumw0 + sumw1 + sumw2 + sumw3
				sumv = sumv0 + sumv1 + sumv2 + sumv3
				if sumw <= W:
					ans = max(ans, sumv)
				if l != len(w[3]):
					sumw3 += minw + 3
					sumv3 += w[3][l]
			if k != len(w[2]):
				sumw2 += minw + 2
				sumv2 += w[2][k]
		if j != len(w[1]):
			sumw1 += minw + 1
			sumv1 += w[1][j]
	if i != len(w[0]):
		sumw0 += minw
		sumv0 += w[0][i]
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, W = map(int, input().split())
w0, w1, w2, w3 = [], [], [], []
base_w = -1
for i in range(N):
    w, v = map(int, input().split())
    if base_w < 0:
        base_w = w

    # 重みごとの箱にいれる
    w -= base_w
    if w == 0:
        w0.append(v)
    elif w == 1:
        w1.append(v)
    elif w == 2:
        w2.append(v)
    else:
        w3.append(v)

# 降順ソート
w0.sort(reverse=True)
w1.sort(reverse=True)
w2.sort(reverse=True)
w3.sort(reverse=True)

# 累積和
w0 = [0] + list(accumulate(w0))
w1 = [0] + list(accumulate(w1))
w2 = [0] + list(accumulate(w2))
w3 = [0] + list(accumulate(w3))

ans = 0
for i0 in range(len(w0)):
    for i1 in range(len(w1)):
        for i2 in range(len(w2)):
            for i3 in range(len(w3)):
                if base_w * i0 + (base_w + 1) * i1 + (base_w + 2) * i2 + (base_w + 3) * i3 > W:
                    continue
                ans = max(ans, w0[i0] + w1[i1] + w2[i2] + w3[i3])

print(ans)