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:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,W = [int(i) for i in readline().split()]
wv = [[int(i) for i in readline().split()] for j in range(n)]

w0 = wv[0][0]

d = [[] for i in range(4)]
for w,v in wv:
    d[w-w0].append(v)

from itertools import accumulate
ac = [None]*4
for i in range(4):
    d[i].sort(reverse=True)
    ac[i] = list(accumulate([0]+d[i]))

#print(d)
#print(ac)

ans = 0
di = len(ac[0])
dj = len(ac[1]) 
dk = len(ac[2]) 
dl = len(ac[3])

ac3 = ac[3]
for i in range(di):
    for j in range(min(n+1-i,dj)):
        for k in range(min(n+1-i-j,dk)):
            Wres = i*w0 + j*(w0+1) + k*(w0+2)
            if Wres > W: continue

            res = ac[0][i] + ac[1][j] + ac[2][k]
            idx = (W-Wres)//(w0+3)
            res += ac3[min(dl-1,idx)]
            if ans < res:
                ans = res

print(ans)

Submission status: Accepted

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

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

s = [[] for _ in range(4)]
w0 = wv[0][0]
for w, v in wv :
    s[w-w0].append(v)
for i in range(4) :
    s[i].sort(reverse=True)
    s[i] = [0] + s[i]
    for j in range(1, len(s[i])) :
        s[i][j] += s[i][j-1]

M = 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 i0*w0+i1*(w0+1)+i2*(w0+2)+i3*(w0+3) <= W :
                    M = max(M, s[0][i0]+s[1][i1]+s[2][i2]+s[3][i3])
                    
print(M)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
w1,v1=map(int,input().split())
l1=[v1]
l2=[]
l3=[]
l4=[]
for _ in range(n-1):
    p=[int(i) for i in input().split()]
    if p[0]==w1:
        l1.append(p[1])
    if p[0]==w1+1:
        l2.append(p[1])
    if p[0]==w1+2:
        l3.append(p[1])
    if p[0]==w1+3:
        l4.append(p[1])
l1.sort()
l2.sort()
l3.sort()
l4.sort()
l1.reverse()
l2.reverse()
l3.reverse()
l4.reverse()
ans=0
for a in range(len(l1)+1):
    for b in range(len(l2)+1):
        for c in range(len(l3)+1):
            for d in range(len(l4)+1):
                if a*w1+b*(w1+1)+c*(w1+2)+d*(w1+3)<=w:
                    ans=max(ans,sum(l1[:a])+sum(l2[:b])+sum(l3[:c])+sum(l4[:d]))
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w = []
v = []
for i in range(N):
    wi, vi = map(int, input().split())
    w.append(wi)
    v.append(vi)
ww = [w[0], w[0]+1, w[0]+2, w[0]+3]
d = {}
for i in range(4):
    d[ww[i]] = []
for i in range(N):
    d[w[i]].append(v[i])
for i in range(4):
    d[ww[i]] = sorted(d[ww[i]], reverse=True)
    
ans = 0
for i in range(N+1):
    if len(d[ww[0]]) < i:
        # print('break i: {}'.format(i))
        break
    for j in range(N+1):
        if i + j > N or len(d[ww[1]]) < j:
            # print('break i, j: {}, {}'.format(i, j))
            break
        for k in range(N+1):
            if i + j + k > N or len(d[ww[2]]) < k:
                # print('break i, j, k: {}, {}, {}'.format(i, j, k))
                break
            for l in range(N+1):
                # print(ww[0] * i + ww[1] * j + ww[2] * k + ww[3] * l)

                if i + j + k + l > N or\
                        len(d[ww[3]]) < l or\
                        ww[0] * i + ww[1] * j +\
                        ww[2] * k + ww[3] * l > W:
                    # print('break i, j, k: {}, {}, {}, {}'.format(i, j, k, l))
                    break

                av = sum([d[ww[0]][p] for p in range(i)])
                bv = sum([d[ww[1]][p] for p in range(j)])
                cv = sum([d[ww[2]][p] for p in range(k)])
                dv = sum([d[ww[3]][p] for p in range(l)])
                ans = max(ans, av+bv+cv+dv)
print(ans)

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,W=map(int,input().split())
w_1,v=map(int,input().split())
w_list=[[] for i in range(4)]
w_list[0].append(v)
for i in range(n-1):
    w,v=map(int,input().split())
    w_list[w-w_1].append(v)
w_cum=[[] for i in range(4)]
for i in range(4):
    w_list[i].sort(reverse=True)
    Sum=0
    w=w_1+i
    for j in range(len(w_list[i])):
        w_cum[i].append((Sum,w*j))
        Sum+=w_list[i][j]
    w_cum[i].append((Sum,w*len(w_list[i])))
a,b,c,d=len(w_cum[0]),len(w_cum[1]),len(w_cum[2]),len(w_cum[3])
ans=0
for h in range(a):
    for i in range(b):
        for j in range(c):
            for k in range(d):
                weight=w_cum[0][h][1]+w_cum[1][i][1]+w_cum[2][j][1]+w_cum[3][k][1]
                if weight<=W:
                    temp=w_cum[0][h][0]+w_cum[1][i][0]+w_cum[2][j][0]+w_cum[3][k][0]
                    ans=max(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in [0]*n]
d={0:0}
for w,v in wv:
    temp=dict()
    for k,i in d.items():
        if k+w in d.keys():
            temp[k+w]=max(d[k+w],i+v)
        else:
            temp[k+w]=i+v
    d.update(temp)
    s=sorted(d.keys())
    m=-1
    for i in s:
        if d[i]<=m:
            del d[i]
        else:
            m=d[i]
print(max([v for w,v in d.items() if w<=W]+[0]))

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    wv = {0: 0}
    for _ in range(N):
        w, v = map(int, input().split())
        kw = sorted(list(wv.keys()), reverse=True)
        for k in kw:
            if k + w not in wv:
                wv[k + w] = wv[k] + v
            else:
                wv[k + w] = max(wv[k + w], wv[k] + v)
    kw = sorted(list(wv.keys()))
    ans = 0
    for k in kw:
        if k > W:
            break
        ans = max(ans, wv[k])
    print(ans)


main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = []
for _ in range(N):
    w, v = map(int, input().split())
    wv.append((w, v))
memo = [{} for _ in range(N + 1)]


def f(i, j):
    if 0 >= i or 0 >= j:
        return 0
    if j in memo[i]:
        return memo[i][j]
    w, v = wv[i - 1]
    t = f(i - 1, j)
    if j - w >= 0:
        t = max(t, f(i - 1, j - w) + v)
    memo[i][j] = t
    return t


def main():
    print(f(N, W))


main()

Submission status: Accepted

Solution code:
#メモ化再帰
N,W = map(int,input().split())
WV = [list(map(int,input().split())) for _ in [0]*N]
memo = [{} for _ in [0]*(N+1)]
def dp(i,j):
    if j<=0 or i<=0: return 0
    if j in memo[i]:return memo[i][j]
    w,v = WV[i-1]
    ret = dp(i-1,j)
    if j-w>=0: ret = max(ret,dp(i-1,j-w)+v)
    memo[i][j] = ret
    return ret
print(dp(N,W))

Submission status: Accepted

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

#dp[i][n:入れた数][dW:w1からの差分の合計]
dp = [[[0]*(3*N+1) for _ in [0]*(N+1)] for _ in [0]*(N+1)]
w0 = WV[0][0]
for i,wv in enumerate(WV,1):
    w,v = wv
    w -= w0
    for n in range(1,i+1):
        for dW in range(3*N+1):
            if n*w0 + dW > W:break
            if w>dW:
                dp[i][n][dW] = dp[i-1][n][dW]
                continue
            dp[i][n][dW] = max(dp[i-1][n][dW],dp[i-1][n-1][dW-w]+v)
print(max(max(row) for row in dp[-1]))

Submission status: Accepted

Solution code:


def main():
    num, max_weigh = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

    data.sort(key=lambda x: (x[0], -x[1]))
    split_data = []

    pre_data = data[0][0]
    pre_ind = 0
    for i in range(num):
        if pre_data != data[i][0]:
            split_data.append(data[pre_ind:i])
            pre_data = data[i][0]
            pre_ind = i
    split_data.append(data[pre_ind:num])

    while len(split_data) != 4:
        split_data.append([])

    ans = 0

    for i in range(-1, len(split_data[0])):
        if i == -1:
            sum_i = 0
            sum_i_w = 0
        else:
            sum_i += split_data[0][i][1]
            sum_i_w += split_data[0][i][0]
        if sum_i_w > max_weigh:
            break
        ans = max(ans, sum_i)

        for j in range(-1, len(split_data[1])):
            if j == -1:
                sum_j = 0
                sum_j_w = 0
            else:
                sum_j += split_data[1][j][1]
                sum_j_w += split_data[1][j][0]
            if sum_i_w + sum_j_w > max_weigh:
                break
            ans = max(ans, sum_i + sum_j)

            for k in range(-1, len(split_data[2])):
                if k == -1:
                    sum_k = 0
                    sum_k_w = 0
                else:
                    sum_k += split_data[2][k][1]
                    sum_k_w += split_data[2][k][0]
                if sum_i_w + sum_j_w + sum_k_w > max_weigh:
                    break
                ans = max(ans, sum_i + sum_j + sum_k)

                for l in range(-1, len(split_data[3])):
                    if l == -1:
                        sum_l = 0
                        sum_l_w = 0
                    else:
                        sum_l += split_data[3][l][1]
                        sum_l_w += split_data[3][l][0]
                    if sum_i_w + sum_j_w + sum_k_w + sum_l_w > max_weigh:
                        break
                    ans = max(ans, sum_i + sum_j + sum_k + sum_l)

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

DP = [[0] * (3 * N + 1) for _ in range(N + 1)]

for i in range(N):
  for j in range(i, -1, -1):
    for k in range(3 * i, -1, -1):
      kk = k + wv[i][0] - wv[0][0]
      DP[j + 1][kk] = max(DP[j + 1][kk], DP[j][k] + wv[i][1])

ans = 0
for i in range(N + 1):
  if i * wv[0][0] > W:
    break
  for j in range(3 * N + 1):
    if i * wv[0][0] + j > W:
      break
    ans = max(ans, DP[i][j])

print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w, v = [None] * N, [None] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
wmin = w[0]
_w = [[], [], [], []]
for i in range(N):
    _w[w[i] - wmin].append(v[i])
for i in range(4):
    _w[i].sort(reverse = 1)
    for j in range(1, len(_w[i])):
        _w[i][j] += _w[i][j-1]
    _w[i].insert(0, 0)
ans = 0
for c0 in range(len(_w[0])):
    for c1 in range(len(_w[1])):
        for c2 in range(len(_w[2])):
            for c3 in range(len(_w[3])):
                if wmin * (c0 + c1 + c2 + c3) + c1 + 2 * c2 + 3 * c3 <= W:
                    ans = max(ans, _w[0][c0] + _w[1][c1] + _w[2][c2] + _w[3][c3])
print(ans)

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)]
w1 = wv[0][0]
ws = []
ijkl = [0,0,0,0]
for i in range(N):
    w = wv[i][0]
    ijkl[w-w1] += 1
for i in range(ijkl[0]+1):
    for j in range(ijkl[1]+1):
        for k in range(ijkl[2]+1):
            for l in range(ijkl[3]+1):
                w = i*w1+j*(w1+1)+k*(w1+2)+l*(w1+3)
                if w <= W:
                    ws.append(w)
ws = list(set(ws))
ws.sort()
dp = [defaultdict(lambda:-float('inf')) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in ws:
        w,v = wv[i]
        dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
print(max(dp[N].values()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    base = w[0]
    max_w = 3 * N
    dp = [[-1] * (max_w + 1)  for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(N, -1, -1):
            for k in range(max_w, -1, -1):
                if dp[j][k] >= 0:
                    dp[j + 1][k + w[i] - base] = max(dp[j + 1][k + w[i] - base], dp[j][k] + v[i])
    ret = 0
    for j in range(N + 1):
        for k in range(max_w + 1):
            if base * j + k <= W:
                ret = max(ret, dp[j][k])
    print(ret)
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate
N, W = map(int, input().split())
Items = [[] for i in range(4)]

w, v = map(int, input().split())
base_w = w
Items[0].append(v)

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

for i in range(4):
    Items[i] = [0] + sorted(Items[i], reverse=True)
    Items[i] = list(accumulate((Items[i])))


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])):
                if base_w * w0 + (base_w + 1) * w1 + (base_w + 2) * w2 + (base_w + 3) * w3 > W:
                    continue
                tmp_ans = Items[0][w0] + Items[1][w1] + Items[2][w2] + Items[3][w3]
                ans = max(ans, tmp_ans)

print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
w1,v = map(int,input().split())
wv = [[v],[],[],[]]
for i in range(N-1):
    w,v = map(int,input().split())
    wv[w-w1].append(v)
for i in range(4):
    wv[i]=[0] + sorted(wv[i],reverse=True)
# 累積和
for i in range(4):
    for j in range(1,len(wv[i])):
        wv[i][j] += wv[i][j-1]
ans = 0
hoge = [0,0,0,0]
for i in range(len(wv[0])):
    hoge[0] = wv[0][i]
    for j in range(len(wv[1])):
        hoge[1] = wv[1][j]
        for k in range(len(wv[2])):
            hoge[2] = wv[2][k]
            for l in range(len(wv[3])):
                hoge[3] = wv[3][l]
                if w1*(i+j+k+l)+j+2*k+3*l > W:
                    break
                else:
                    ans = max(ans,sum(hoge))
print(ans)

Submission status: Accepted

Solution code:
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, W = list(map(int, sys.stdin.readline().split()))
Ws, Vs = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

Ws = np.array(Ws)
Vs = np.array(Vs)

w1 = Ws[0]
ws = np.arange(4) + w1
v1s = Vs[Ws == ws[0]]
v2s = Vs[Ws == ws[1]]
v3s = Vs[Ws == ws[2]]
v4s = Vs[Ws == ws[3]]
v1s.sort()
v2s.sort()
v3s.sort()
v4s.sort()
v1s = np.concatenate([[0], v1s[::-1].cumsum()])
v2s = np.concatenate([[0], v2s[::-1].cumsum()])
v3s = np.concatenate([[0], v3s[::-1].cumsum()])
v4s = np.concatenate([[0], v4s[::-1].cumsum()])

counts = np.array(list(itertools.product(
    range(len(v1s)),
    range(len(v2s)),
    range(len(v3s)),
    range(len(v4s))
)))
counts = counts[np.dot(counts, ws) <= W]

sums = v1s[counts[:, 0]] + \
       v2s[counts[:, 1]] + \
       v3s[counts[:, 2]] + \
       v4s[counts[:, 3]]

print(sums.max())

Submission status: Accepted

Solution code:
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, W = list(map(int, sys.stdin.readline().split()))
WV = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# dp[w]: w 以下で選ぶときの最大の価値
dp = defaultdict(int)
dp[0] = 0
for w, v in WV:
    for k, d in list(dp.items()):
        dp[k + w] = max(dp[k + w], d + v)

ans = 0
for w, v in dp.items():
    if w <= W:
        ans = max(ans, v)
print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########

N, W = l_inpl()
w, v = [], []
item = [[] for i in range(4)]

for i in range(N):
    wi, vi = l_inpl()
    if i == 0:
        item[0].append(vi)
        w_base = wi
    else:
        item[wi - w_base].append(vi)

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

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

print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, W = MI()
    items = [[] for _ in range(4)]
    w0, v0 = MI()
    items[0].append(v0)
    for _ in range(N-1):
        w, v = MI()
        items[w - w0].append(v)
    
    cumsum = [[0] + list(accumulate(sorted(items[i],reverse=True))) for i in range(4)]
    ans=0
    for i,c0 in enumerate(cumsum[0]):
        for j,c1 in enumerate(cumsum[1]):
            for k,c2 in enumerate(cumsum[2]):
                s = i * w0 + j * (w0 + 1) + k * (w0 + 2)
                if s <= W:
                    l = min(len(cumsum[3])-1,(W-s)//(w0+3))
                    ans = max(ans, c0 + c1 + c2 +cumsum[3][l])
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
def cmb(n, r):
    if n-r<0:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)

def main():
    n,W=map(int,input().split())
    d=defaultdict(int)
    d[0]=0
    for i in range(n):
        w,v=map(int,input().split())
        for k,j in d.copy().items():
            if k+w<=W:
                d[k+w]=max(d[k+w],j+v)
#    print(d)
    print(max(d.values()))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

n, w = map(int, input().split())
d = defaultdict(list)
for i in range(n):
    wi, vi = map(int, input().split())
    d[wi].append(vi)
for key in d.keys():
    di = d[key]
    di.sort(reverse=True)
    a = [0]
    for i in di:
        a.append(a[-1] + i)
    d[key] = a
keys = list(d.keys())
for i in range(4 - len(keys)):
    key = max(keys) + i + 1
    d[key] = [0]
    keys.append(key)
ans = 0
for i in range(min(w // keys[0] + 1, len(d[keys[0]]))):
    wi = w - keys[0] * i
    ai = d[keys[0]][i]
    for j in range(min(wi // keys[1] + 1, len(d[keys[1]]))):
        wj = wi - keys[1] * j
        aj = d[keys[1]][j]
        for k in range(min(wj // keys[2] + 1, len(d[keys[2]]))):
            wk = wj - keys[2] * k
            ak = d[keys[2]][k]
            idx = min(wk // keys[3], len(d[keys[3]]) - 1)
            ans = max(ans, ai + aj + ak + d[keys[3]][idx])
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
wv = {}
for i in range(N):
    w,v = map(int,input().split())
    if w not in wv.keys():
        wv[w] = []
    wv[w].append(v)

for w in wv.keys():
    wv[w] = sorted(wv[w],reverse=True)

wv_ruiseki = {}
for w in wv.keys():
    wv_ruiseki[w] = [0,wv[w][0]]
    for i in range(2,len(wv[w])+1):
        wv_ruiseki[w].append(wv_ruiseki[w][i-1] + wv[w][i-1])


w = []
for i in wv.keys():
    w.append(i)

ans = 0
if len(w) == 1:

    for i in range(len(wv[w[0]])+1):
        if w[0]*i <= W:
            ans = max(ans , wv_ruiseki[w[0]][i])
elif len(w) == 2:

    for i in range(len(wv[w[0]])+1):
        for j in range(len(wv[w[1]])+1):
            if w[0]*i + w[1]*j <= W:
                ans = max(ans , wv_ruiseki[w[0]][i]+ wv_ruiseki[w[1]][j])

elif len(w) == 3:

    for i in range(len(wv[w[0]])+1):
        for j in range(len(wv[w[1]])+1):
            for k in range(len(wv[w[2]])+1):
                if w[0]*i + w[1]*j + w[2]*k <= W:
                    ans = max(ans , wv_ruiseki[w[0]][i]+ wv_ruiseki[w[1]][j] + wv_ruiseki[w[2]][k])
elif len(w) == 4:
    for i in range(len(wv[w[0]])+1):
        for j in range(len(wv[w[1]])+1):
            for k in range(len(wv[w[2]])+1):
                for t in range(len(wv[w[3]])+1):
                    if w[0]*i + w[1]*j + w[2]*k + w[3]*t <= W:
                        ans = max(ans , wv_ruiseki[w[0]][i]+ wv_ruiseki[w[1]][j] + wv_ruiseki[w[2]][k] + wv_ruiseki[w[3]][t])


print(ans)

Submission status: Accepted

Solution code:
# 重さとしてありうるのは4種類
# 重さ0：x個,...
# x+y+z <= N. O(N^3)

N,W = map(int,input().split())
WV = [[int(x) for x in input().split()] for _ in range(N)]
w1 = WV[0][0]
V = [[],[],[],[]]
Vcum = [[0],[0],[0],[0]]

for w,v in WV:
  V[w-w1].append(v)

for i in range(4):
  s = 0
  V[i].sort(reverse = True) # desc
  for x in V[i]:
    s += x
    Vcum[i].append(s)
    

answer = 0
for a in range(len(V[0])+1):
  for b in range(len(V[1])+1):
    for c in range(len(V[2])+1):
      w = w1*a + (w1+1)*b + (w1+2)*c
      if w > W:
        break
      d = min((W-w)//(w1+3),len(V[3]))
      x = Vcum[0][a] + Vcum[1][b] + Vcum[2][c] + Vcum[3][d]
      answer = max(answer,x)
print(answer)

Submission status: Accepted

Solution code:
# 参考：https://atcoder.jp/contests/abc060/submissions/3379570
# Nが高々100までなのでそれぞれ25個ずつある場合が一番場合の数が多いが25**4は10**5オーダーに収まるので問題ない

N, W = map(int, input().split())
# 物を格納
L = [list(map(int, input().split())) for _ in range(N)]

# 一つ目の物の重さが一番小さいので
w_min = L[0][0]

# 4種類の重さについて、価値を格納する
M = [[], [], [], []]
for w, v in L:
      M[w - w_min].append(v)

# それぞれについて価値の高い順に並べる
M0 = sorted(M[0], reverse=True)
M1 = sorted(M[1], reverse=True)
M2 = sorted(M[2], reverse=True)
M3 = sorted(M[3], reverse=True)

ans = 0
# それぞれをp,q,r,s個ずつ鞄に入れる時を考える
for p in range(len(M0)+1):
      for q in range(len(M1)+1):
            for r in range(len(M2)+1):
                  for s in range(len(M3)+1):
                        # 重さが制限を超えないならそれまでの最大価値と比較
                        w = p*(w_min) + q*(w_min+1) + r*(w_min+2) + s*(w_min+3)
                        if w <= W:
                              ans = max(ans, sum(M0[:p])+sum(M1[:q])+sum(M2[:r])+sum(M3[:s]))

print(ans)

Submission status: Accepted

Solution code:
N,W = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ] for i in range(N) ]

lic = [[],[],[],[]]
mi = li[0][0]
for w,v in li:
  lic[w-mi].append(v)

[ lis.sort() for lis in lic ]
[ lis.reverse() for lis in lic ]


for j in range(4):
  pli = lic[j]
  for i in range( len(pli) - 1 ):
    pli[i+1] += pli[i]
for i in range(4):
  tmp = [0]
  tmp.extend(lic[i])
  lic[i] = tmp 
    

sm = 0
for i in range( len(lic[0]) ):
  for j in range( len(lic[1]) ):
    for k in range( len(lic[2]) ):
      for l in range( len(lic[3]) ):
        w = (mi)*(i) + (mi+1)*(j) + (mi+2)*(k) + (mi+3)*(l)
        v = lic[0][i]+lic[1][j]+lic[2][k]+lic[3][l]
        if w <= W:
          sm = max(sm,v)
print ( sm )

Submission status: Accepted

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

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

from collections import defaultdict
DP = defaultdict(int)
DP[0]=0

for w,v in S:
    for w2 in sorted(DP.keys(),reverse=True):
        if w+w2<=W:
            DP[w+w2]=max(DP[w+w2],DP[w2]+v)

print(max(DP.values()))

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

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

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

w_sum = [0 for i in range(N+1)]
v_sum = [0 for i in range(N+1)]

w.insert(0,0)
v.insert(0,0)

for i in range(N):
    w_sum[i+1] = w_sum[i]+w[i+1]
    v_sum[i+1] = v_sum[i]+v[i+1]


nap_memo = {}

def nap(i,W2):#i:count_pieces,W2:rest_weight
    key = str(i)+":"+str(W2)
    if key in nap_memo:
        return nap_memo[key]
    elif i == 0:#品物０個の時は価値０
        r = 0
    elif W2 < w[0]:
        r = 0
    elif W2 < w[i]:#i番目の荷物が残量を超えるなら入らない
        r = nap(i-1,W2)
    elif w_sum[i] <= W2:
        r = v_sum[i]
    else:
        r = max(nap(i-1,W2-w[i])+v[i], nap(i-1,W2))

    nap_memo[key] = r
    return r


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

Submission status: Accepted

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

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

values = [[] for _ in range(4)]

values[0].append(v)

for _ in range(N-1):
    x, y = map(int, input().split())
    values[x-w].append(y)

n = [0]*4
for i in range(4):
    n[i] = len(values[i])
    values[i].sort(reverse=1)

ans = 0
ans0 = 0
ans1 = 0
ans2 = 0
for n0 in range(n[0]+1):
    if n0 > 0:
        ans0 += values[0][n0-1]
    if n0 * w > W:
        break
    for n1 in range(n[1]+1):
        if n1 > 0:
            ans1 += values[1][n1-1]
        else:
            ans1 = 0
        if n0 * w + n1 * (w+1) > W:
            break
        for n2 in range(n[2]+1):
            ww = n0 * w + n1 * (w+1) + n2 * (w+2)
            if n2 > 0:
                ans2 += values[2][n2-1]
            else:
                ans2 = 0
            if ww > W:
                break
            n3 = (W - ww) // (w+3)
            ans = max(ans, ans0+ans1+ans2+sum(values[3][:n3]))

print(ans)

Submission status: Accepted

Solution code:
import functools
from collections import*
@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:
N,W=map(int,input().split())
from collections import*
d=defaultdict(int)
d[0]=0
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)
print(max(d.values()))