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
from collections import defaultdict
input = sys.stdin.buffer.readline

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

pre_dp = defaultdict(lambda: 0)
pre_dp[0] = 0

for i in range(1, n+1):
    cur_dp = defaultdict(lambda: 0)
    w_i, v_i = wv[i-1]

    keys = sorted(pre_dp.keys())
    for k in keys:
        cur_dp[k] = max(cur_dp[k], pre_dp[k])
        if k + w_i <= W:
            big = max(pre_dp[k + w_i], pre_dp[k] + v_i)
            cur_dp[k+w_i] = big
    pre_dp = cur_dp
ans = 0
for w, v in cur_dp.items():
    if w <= W:
        ans = max(ans, v)

print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
mw = wv[0][0]
wv.sort(key=lambda x: -x[1])
values = [[] for _ in range(4)]
for w, v in wv:
    values[w-mw].append(v)


def solve(n, w, c):
    if n >= 4 or w >= W or c >= N:
        return 0
    r = 0
    for i in range(len(values[n])+1):
        cw = w + (mw + n) * i
        cc = c + i
        if cw <= W and cc <= N:
            r = max(r, sum(values[n][0:i]) + solve(n+1, cw, cc))
    return r


print(solve(0, 0, 0))

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
tmpv = [[] for _ in range(4)]
w1 = None
for i in range(N):
    tw, tv = map(int,input().split())
    if i==0:
        w1 = tw
        tmpv[0].append(tv)
    else:
        tmpv[tw-w1].append(tv)

v = []
for tv in tmpv:
    v.append(sorted(tv, reverse=True)+[0])
    
ans = 0
for i in range(len(v[0])):
  for j in range(len(v[1])):
    for k in range(len(v[2])):
      for l in range(len(v[3])):
        tw = w1*i+(w1+1)*j+(w1+2)*k+(w1+3)*l
        tv = sum(v[0][:i]) + sum(v[1][:j]) + sum(v[2][:k]) + sum(v[3][:l])
        if tw<=W:
          ans = max(ans, tv)
print(ans)

Submission status: Accepted

Solution code:
n, W = map(int, input().split())
w1, w2, w3, w4 = [], [], [], []
w, v = map(int, input().split())
w1.append(v)

# 4パターンしかない
for _ in range(n-1):
    a, b = map(int, input().split())
    if a == w:
        w1.append(b)
    if a == w+1:
        w2.append(b)
    if a == w+2:
        w3.append(b)
    if a == w+3:
        w4.append(b)
        
# 降順にする
for w_ in [w1, w2, w3, w4]:
    w_.sort(reverse= True)
    
ans = 0
for i in range(0, len(w1)+1):
    for j in range(0, len(w2)+1):
        for k in range(0, len(w3)+1):
            # w4を詰める前にチェック
            res = W - (i * w + j * (w+1) + k * (w+2))
            if res < 0:
                continue
            # w4は詰めれるだけ詰める
            tmp = sum(w1[:i])+sum(w2[:j])+sum(w3[:k])+sum(w4[:res//(w+3)])
            ans = max(tmp, ans)
            
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,W = map(int, input().split())
    w,v = [], []
    for i in range(n):
        a,b = map(int, input().split())
        if i == 0:
            w.append(a)
        else:
            w.append(a - w[0])
        v.append(b)
    #w1の重さ
    base = w[0]
    w[0] = 0
    w0, w1, w2, w3 = [], [], [], []
    for i in range(n):
        if w[i] == 0:
            w0.append(v[i])
        if w[i] == 1:
            w1.append(v[i])
        if w[i] == 2:
            w2.append(v[i])
        if w[i] == 3:
            w3.append(v[i])
    w0.sort(reverse=1)
    w1.sort(reverse=1)
    w2.sort(reverse=1)
    w3.sort(reverse=1)
    w0 = [0] + w0
    w1 = [0] + w1
    w2 = [0] + w2
    w3 = [0] + w3
    w0 = list(accumulate(w0))
    w1 = list(accumulate(w1))
    w2 = list(accumulate(w2))
    w3 = list(accumulate(w3))

    res = 0
    for i in range(len(w0)):
        for j in range(len(w1)):
            for k in range(len(w2)):
                for l in range(len(w3)):
                    if base*(i+j+k+l) + j + k*2 + l*3 <= W:
                        res = max(res, w0[i]+w1[j]+w2[k]+w3[l])
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, W, *WV = map(int, open(0).read().split())

C = {0: 0}
for v, w in zip(*[reversed(WV)] * 2):
    for x, y in C.copy().items():
        if x + w <= W:
            C[x + w] = max(C.get(x + w, 0), y + v)

print(max(C.values()))

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

w1=wv[0][0]
wv.sort()
lst=[[],[],[],[]]
for i in range(n):
    w,v=wv[i]
    lst[w-w1].append(v)
# print(lst)
ruilst=[]
for i in range(4):
    ruilst.append(ruiseki(lst[i][::-1]))
# print(ruilst)

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

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

dp=[[-float('inf')]*101*400 for i in range(n+1)]
dp[0][0]=0

kijun=wv[0][0]
for i in range(n):
    for j in range(101*400):
        if dp[i][j]!=-float('inf'):
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])
            ko,a=j//400,j%400
            dp[i+1][(ko+1)*400+a+wv[i][0]-kijun]=max(dp[i+1][(ko+1)*400+a+wv[i][0]-kijun],dp[i][j]+wv[i][1])

ans=0
for i in range(101*400):
    ko,a=i//400,i%400
    if ko*kijun+a<=w:
        ans=max(ans,dp[n][i])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(N)]
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:
import itertools
from collections import defaultdict

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

for i in d:
    d[i] = list(itertools.accumulate(sorted(d[i], reverse=True)))
mm = min(d)

ans = 0
for t in itertools.product(range(len(d[mm]) + 1), range(len(d[mm + 1]) + 1),
                           range(len(d[mm + 2]) + 1), range(len(d[mm + 3]) + 1)):
    if sum((mm + i) * t[i] for i in range(4)) > W:
        continue
    ans = max(ans, sum(d[mm + i][t[i] - 1] if t[i] else 0 for i in range(4)))
print(ans)

Submission status: Accepted

Solution code:
#060_D
n, W = map(int, input().split())
w1, w2, w3, w4 = [], [], [], []
w, v = map(int, input().split())
w1.append(v)
for _ in range(n-1):
    a, b = map(int, input().split())
    if a == w: w1.append(b)
    if a == w+1: w2.append(b)
    if a == w+2: w3.append(b)
    if a == w+3: w4.append(b)
    
for w_ in [w1, w2, w3, w4]:
    w_.sort(reverse= True)
    
ans = 0
for i in range(0, len(w1)+1):
    for j in range(0, len(w2)+1):
        for k in range(0, len(w3)+1):
            res = W - (i * w + j * (w+1) + k * (w+2))
            if res < 0:
                continue
            tmp = sum(w1[:i])+sum(w2[:j])+sum(w3[:k])+sum(w4[:res//(w+3)])
            ans = max(tmp, ans)
            
print(ans)

Submission status: Accepted

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

w0,v0 = map(int,input().split())
vlist = [[v0],[],[],[]]

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

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

m = 0
S = [[0],[0],[0],[0]]
for i in range(4):
    for j in range(len(vlist[i])):
        S[i].append(S[i][-1]+vlist[i][j])

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

#print(vlist)
#print(S)
print(m)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

rl = sys.stdin.readline


def solve():
    N, W = map(int, rl().split())
    w1, w2, w3, w4 = [[0, 0]], [[0, 0]], [[0, 0]], [[0, 0]]
    w1.append(list(map(int, rl().split())))
    min_w = w1[1][0]
    for _ in range(N - 1):
        w, v = map(int, rl().split())
        d = w - min_w
        if d == 0:
            w1.append([w, v])
        elif d == 1:
            w2.append([w, v])
        elif d == 2:
            w3.append([w, v])
        else:
            w4.append([w, v])
    w1.sort(key=itemgetter(1), reverse=True)
    w2.sort(key=itemgetter(1), reverse=True)
    w3.sort(key=itemgetter(1), reverse=True)
    w4.sort(key=itemgetter(1), reverse=True)
    
    ans = 0
    for i in range(len(w1)):
        w_tmp1, v_tmp1 = 0, 0
        for j in range(i):
            w_tmp1 += w1[j][0]
            v_tmp1 += w1[j][1]
        for j in range(len(w2)):
            w_tmp2, v_tmp2 = w_tmp1, v_tmp1
            for k in range(j):
                w_tmp2 += w2[k][0]
                v_tmp2 += w2[k][1]
            for k in range(len(w3)):
                w_tmp3, v_tmp3 = w_tmp2, v_tmp2
                for l in range(k):
                    w_tmp3 += w3[l][0]
                    v_tmp3 += w3[l][1]
                for l in range(len(w4)):
                    w_tmp4, v_tmp4 = w_tmp3, v_tmp3
                    for m in range(l):
                        w_tmp4 += w4[m][0]
                        v_tmp4 += w4[m][1]
                    if w_tmp4 <= W:
                        ans = max(ans, v_tmp4)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
wv=[[]for _ in range(4)]
for i in range(n):
	w,v=map(int,input().split())
	if i==0:
		r=w
		wv[0].append(v)
	else:
		wv[w-r].append(v)
for i in range(4):
	wv[i].sort(reverse=True)
	for j in range(len(wv[i])-1):
		wv[i][j+1]+=wv[i][j]
	wv[i].insert(0,0)
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])):
				p=wv[0][i]+wv[1][j]+wv[2][k]+wv[3][l]
				if i*r+j*(r+1)+k*(r+2)+l*(r+3)<=W:
					ans=max(ans,p)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
sys.setrecursionlimit(100000000)
from bisect import bisect_right

def main():
    n,w = map(int,input().split())
    minw,u = map(int,input().split())
    item = {minw:[u],minw + 1:[],minw + 2:[], minw + 3:[]}
    for _ in range(n - 1):
        wei,u = map(int,input().split())
        item[wei].append(u)
    
    l = [0] * 4
    keys = sorted(item.keys())
    i = 0
    for k in keys:
        item[k].sort(reverse = True)
        l[i] = len(item[k])
        i += 1
    
    X = set()
    for i in range(l[0] + 1):
        if i == 0:
            cumsum = 0
        else:
            cumsum += item[minw][i - 1]
        cumsumx = cumsum
        for j in range(l[1] + 1):
            weight = minw * i + (minw + 1) * j 
            if j != 0:
                cumsumx += item[minw + 1][j - 1]
            if weight <= w:
                X.add((weight, cumsumx))

    Y = []
    for i in range(l[2] + 1):
        if i == 0:
            cumsum = 0
        else:
            cumsum += item[minw + 2][i - 1]
        cumsumy = cumsum
        for j in range(l[3] + 1):
            weight = (minw + 2) * i + (minw + 3) * j
            if j != 0:
                cumsumy += item[minw  + 3][j - 1]
            if weight <= w:
                Y.append((weight, cumsumy))
    
    Y.sort(key = lambda x:x[0])
    Yw = [0] * len(Y)
    cummax = [0] * len(Y)
    for i in range(len(Y)):
        if i == 0:
            cummax[i] = Y[i][1]
            Yw[i] = Y[i][0]
        else:
            cummax[i] = max(cummax[i - 1],Y[i][1])
            Yw[i] = Y[i][0]
    
    ans = 0
    for x in X:
        wei,va = x
        idx = bisect_right(Yw,w - wei)
        if idx == 0:
            continue
        else:
            ans = max(ans,cummax[idx - 1] + va)
    
    print(ans)
    
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
l=[0]*4
s=[[] for i in range(4)]
for i in range(N):
    w,v=map(int,input().split())
    if w in l:
        s[l.index(w)].append(v)
    else:
        for i in range(4):
            if l[i]==0:
                l[i]=w
                s[i].append(v)
                break
g=[[0] for i in range(4)]
for i in range(4):
    s[i].sort(reverse=1)
    t=0
    for j in s[i]:
        t+=j
        g[i].append(t)
a=0
for i in range(len(g[0])):
    for j in range(len(g[1])):
        for k in range(len(g[2])):
            for m in range(len(g[3])):
                if i*l[0]+j*l[1]+k*l[2]+m*l[3]>W:
                    continue
                t=g[0][i]+g[1][j]+g[2][k]+g[3][m]
                if t>a:
                    a=t
print(a)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc060/tasks/arc073_b
# 典型的なナップサック。だけど配列が大きいので素直に実装するとTLEになる
# 成約により、w1以上は必ず前のjを見ることに注意するとテーブルのサイズがぐっと減ることに気がつくがこれを実装するのはなかなかめんどくさそう。
# defaltdictを利用した再帰メモ化なら比較的実装可能では？

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


N, W = read_ints()
w, v = read_col(N, 2)

from collections import defaultdict
dp = defaultdict(lambda: -1)


def f(i, j):  # i番目を含んで考慮したとき重さjまでで達成できる価値の最大値
    if dp[i, j] != -1:
        return dp[i, j]
    if i == -1:
        return 0
    if j - w[i] < 0:
        return f(i - 1, j)

    ret = max(f(i - 1, j - w[i]) + v[i], f(i - 1, j))
    dp[i, j] = ret
    return ret


print(f(N - 1, W))

Submission status: Accepted

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

for _ in range(N):
    wv.append(tuple(map(int, input().split())))

# dp[i][j] i 番目まで、 重さ j で最大化した価値
# 答え: dp[N][W]
# 初期: dp[0][j] = 0
#       dp[i][0] = 0
#
# dp[i+1][j] = 品物i+1 を使わない場合、 dp[i][j]
#               品物i+1 を使う場合、 dp[i][j-w_{i+1}] + v_{i+1}
# i

memo = {}

def dfs(i, j):
    if (i,j) in memo:
        return memo[(i,j)]

    if i < 0 or j <= 0:
        return 0

    ret = 0
    wi, vi = wv[i]
    if j-wi < 0:
        ret = dfs(i-1, j)
    else:
        ret = max(dfs(i-1, j), dfs(i-1, j-wi) + vi)

    memo[(i,j)] = ret

    return ret

print(dfs(N-1, W))

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
  w[i],v[i]=map(int,input().split())
ws=w[0]
V=[[] for i in range(4)]
for i in range(n):
  V[w[i]-ws].append(v[i])
V[0].sort(reverse=True)
V[1].sort(reverse=True)
V[2].sort(reverse=True)
V[3].sort(reverse=True)
VV=[[0] for i in range(4)]
for i in range(4):
  for j in range(len(V[i])):
    VV[i].append(VV[i][-1]+V[i][j])
ans=0
for i in range(len(V[0])+1):
  for j in range(len(V[1])+1):
    for k in range(len(V[2])+1):
      for l in range(len(V[3])+1):
        if i*ws+j*(ws+1)+k*(ws+2)+l*(ws+3)>W:
          break
        if VV[0][i]+VV[1][j]+VV[2][k]+VV[3][l]>ans:
          ans=VV[0][i]+VV[1][j]+VV[2][k]+VV[3][l]
print(ans)

Submission status: Accepted

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

base = a[0][0]
s = [[] for _ in range(4)]
for w, v in a:
    s[w-base].append(v)
for i in range(4):
    s[i].sort(reverse=True)

length = [len(s[i]) for i in range(4)]
cum = [[] for _ in range(4)]
for i in range(4):
    cum[i] = [0 for _ in range(length[i]+1)]
    for j in range(length[i]):
        cum[i][j+1] = cum[i][j] + s[i][j]

ans = 0
for i in range(length[0]+1):
    for j in range(length[1]+1):
        for k in range(length[2]+1):
            for l in range(length[3]+1):
                weight = (i+j+k+l) * base + j + 2*k + 3*l
                if weight <= W:
                    ans = max(ans, cum[0][i] + cum[1][j] + cum[2][k] + cum[3][l])
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
def saiki(value,HP,num):
    if num==0:
        #print(HP//base)
        value+=wa[0][min(HP//base,len(wa[0])-1)]
        ans.append(value)
    else:
        for i in range(len(wa[num])):
            if HP-(num+base)*i>=0:
                saiki(value+wa[num][i],HP-(num+base)*i,num-1)
            else:
                break
    return


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

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

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

lis=list(map(lambda x:sorted(x, reverse=True),lis))

wa=[[0] for i in range(4)]

for i in range(len(wa)):
    for item in lis[i]:
        wa[i].append(wa[i][-1]+item)

#print(wa)

ans=[]
saiki(0,W,3)
    

print(max(ans))

Submission status: Accepted

Solution code:
import  numpy as np
N, W, *L = map(int, open(0).read().split())
M = 3*(N-1)+1
dp = np.zeros((M,N+1),np.int64)
for w,v in zip(*[iter(L)]*2):
  w -= L[0]
  dp[w:,1:] = np.maximum(dp[w:,1:], dp[:M-w,:N]+v)

ans = 0
for i in range(N+1):
  m = i*L[0]
  if m>W:
    continue
  m = min(W-m,M-1)
  ans = max(ans, dp[m,i])
print(ans)

Submission status: Accepted

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

N, W = [int(x) for x in input().split()]
wv = []
for _ in range(N):
    wv.append([int(x) for x in input().split()])
w1 = wv[0][0]
dp = [[[0] * (N + 1) for _ in range(4 * N + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    w, v = wv[i - 1]
    w -= (w1 - 1)
    for j in range(4 * N + 1):
        for k in range(1, N + 1):
            if j - w >= 0:
                dp[i][j][k] = max(dp[i - 1][j - w][k - 1] + v, dp[i - 1][j][k])
            else:
                dp[i][j][k] = dp[i - 1][j][k]
ans = 0
for i in range(N + 1):
    for j in range(4 * N + 1):
        for k in range(N + 1):
            if W - (w1 - 1) * k >= j:
                ans = max(ans, dp[i][j][k])

print(ans)

Submission status: Accepted

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

value_table = [[] for i in range(4)]
for i in range(N):
    w, v = map(int,input().split())
    if i == 0:
        w1 = w
    value_table[w-w1] += [v]

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

ans = 0
value_table_ruiseki = [[0] for i in range(4)]
for i in range(4):
    for v in value_table[i]:
        value_table_ruiseki[i] += [value_table_ruiseki[i][-1] + v]

ans = 0
for i, iv in enumerate(value_table_ruiseki[0]):
    for j, jv in enumerate(value_table_ruiseki[1]):
        for k, kv in enumerate(value_table_ruiseki[2]):
            for ell, ellv in enumerate(value_table_ruiseki[3]):
                weight = i*w1 + j*(w1+1) + k*(w1+2) + ell*(w1+3)
                value = iv + jv + kv + ellv
                if weight <=W:
                    ans = max(ans, value)

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)]

dp = defaultdict(int)
dp[0] = 0

for w, v in wv:
    for k in sorted(dp.keys(), reverse=True):
        if k + w <= W:
            dp[k + w] = max(dp[k + w], dp[k] + v)

ans = max(dp.values())
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

w1 = wv[0][0]
weights = [[] for _ in range(4)]

for w, v in wv:
    w_diff = w - w1
    weights[w_diff].append(v)

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

acc = [[0] + list(accumulate(li)) for li in weights]

l3 = len(weights[3])
ans = 0
for i, e1 in enumerate(acc[0]):
    for j, e2 in enumerate(acc[1]):
        for k, e3 in enumerate(acc[2]):
            w_sm = w1 * i + (w1 + 1) * j + (w1 + 2) * k
            if w_sm > W:
                break

            l = min((W - w_sm) // (w1 + 3), l3)
            val = acc[0][i] + acc[1][j] + acc[2][k] + acc[3][l]
            ans = max(ans, val)

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

w1 = wv[0][0]
weights = [[] for _ in range(4)]

for w, v in wv:
    w_diff = w - w1
    weights[w_diff].append(v)

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

acc = [[0] + list(accumulate(li)) for li in weights]

ans = 0
for i, e1 in enumerate(acc[0]):
    for j, e2 in enumerate(acc[1]):
        for k, e3 in enumerate(acc[2]):
            for l, e4 in enumerate(acc[3]):
                if w1 * i + (w1 + 1) * j + (w1 + 2) * k + (w1 + 3) * l <= W:
                    ans = max(ans, e1 + e2 + e3 + e4)

print(ans)

Submission status: Accepted

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

dp = [[[-1] * (3 * n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 0
w1 = wv[0][0]

for i, (w, v) in enumerate(wv):
    for j in range(i + 1):
        for k in range(3 * n + 1):
            if dp[i][j][k] != -1:
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
                w_diff = w - w1
                if j + 1 <= n and k + w_diff <= 3 * n:
                    dp[i+1][j+1][k+w_diff] = max(dp[i+1][j+1][k+w_diff], dp[i][j][k] + v)

ans = 0
for j in range(n + 1):
    w_diff_mx = min(W - w1 * j, 3 * n)
    for k in range(w_diff_mx + 1):
        ans = max(ans, dp[n][j][k])

print(ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

import bisect

def main():
    mod=10**9+7
    N,W=MI()
    w=[0]*N
    v=[0]*N
    for i in range(N):
        w[i],v[i]=MI()
    w1=w[0]
    for i in range(N):
        w[i]-=w1
        
    a=set([0])
    for i in range(N+1):
        for j in range(3*i+1):
            ww=w1*i+j
            if ww>W:
                break
            a.add(ww)
    a=list(a)
    a.sort()#sortしないと順番がぐちゃぐちゃになっている？かも
    M=len(a)
    
    
    #dp[i][j]はiまでの商品で,重さa[j]のときの価値の最大
    dp=[[-1]*(M) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0]=0
    ans=0
    
    for i in range(N):
        for j in range(M):
            if dp[i][j]!=-1:
                dp[i+1][j]=max(dp[i+1][j],dp[i][j])
                ww=a[j]+w1+w[i]
                if ww<=W:
                    jj=bisect.bisect_left(a,ww)
                    dp[i+1][jj]=max(dp[i+1][jj],dp[i][j]+v[i])
                    ans=max(ans,dp[i+1][jj])
                    
    print(ans)
                    
    
            

main()

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

import bisect

def main():
    mod=10**9+7
    N,W=MI()
    w=[0]*N
    w2=[0,0,0,0]#結局4通りしかない
    v2=[[] for _ in range(4)]
    v=[0]*N
    for i in range(N):
        w[i],v[i]=MI()
    w1=w[0]
    for i in range(N):
        w[i]-=w1
        w2[w[i]]+=1
        v2[w[i]].append(v[i])
        
    for i in range(4):
        v2[i].sort(reverse=True)
        
    s=[[0] for _ in range(4)]
    for i in range(4):
        for j in range(len(v2[i])):
            s[i].append(s[i][-1]+v2[i][j])
     
    ans=0       
    for a in range(len(s[0])):
        for b in range(len(s[1])):
            for c in range(len(s[2])):
                for d in range(len(s[3])):
                    ww=b+2*c+3*d+w1*(a+b+c+d)
                    if ww<=W:
                        temp=s[0][a]+s[1][b]+s[2][c]+s[3][d]
                        ans=max(ans,temp)
                        
    print(ans)
                        
        
    

main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,W=map(int,input().split())
dp=[[-1]*301 for i in range(N+1)]
dp[0][0]=0

for i in range(N):
    w,v=map(int,input().split())
    if i==0:
        base=w
    for i in range(N)[::-1]:
        for j in range(301)[::-1]:
            if dp[i][j]!=-1:
                dp[i+1][j+w-base]=max(dp[i][j]+v,dp[i+1][j+w-base])

ans=0
for index,item in enumerate(dp):
    if W-index*base+1<=0:
        break
    ans=max(max(item[:W-index*base+1]),ans)
    #print(item[:W-index*base+1])

print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    import bisect

    N, W = read_values()
    I = [tuple(read_values()) for _ in range(N)]

    init_w = I[0][0]
    D = {i: [] for i in range(4)}
    S = {i: [0] for i in range(4)}
    for w, v in I:
        bisect.insort(D[w - init_w], -v)

    for i, d in D.items():
        for v in d:
            S[i].append(v + S[i][-1])

    res = 0
    for t0 in range(len(D[0]) + 1):
        for t1 in range(len(D[1]) + 1):
            for t2 in range(len(D[2]) + 1):
                for t3 in range(len(D[3]) + 1):
                    if (t0 + t1 + t2 + t3) * init_w + t1 + 2 * t2 + 3 * t3 > W:
                        continue

                    res = min(res, S[0][t0] + S[1][t1] + S[2][t2] + S[3][t3])
    print(-res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N, W = read_values()
    dp = [
        [[0 for _ in range(N * 3 + 10)] for __ in range(N + 10)]
        for ___ in range(N + 10)
    ]
    I = [tuple(read_values()) for _ in range(N)]

    w0 = I[0][0]
    if w0 > W:
        print(0)
        return

    for i, (w1, v) in enumerate(I):
        w = w1 - w0
        for k in range(N):
            for j in range(N * 3 + 5):
                dp[i + 1][k][j] = max(dp[i][k][j], dp[i + 1][k][j])
                dp[i + 1][k + 1][j + w] = max(dp[i][k][j] + v, dp[i + 1][k + 1][j + w])

    res = 0
    for k in range(N + 1):
        r = min(W - k * w0, 3 * N + 5)
        if r < 0:
            continue
        for i in range(r + 1):
            res = max(res, dp[N][k][i])
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
wv=[]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    wv.append([a,b])
    v.append(b)
v.sort(reverse=True)
ans=0
w0=wv[0][0]
wp=3*n+1
dp=[[-1 for jjj in range(n+1)] for iii in range(3*n+1)]
dp[0][0]=0
for i in range(n):
    for jj in range(n-1,-1,-1):
        for k in range(wp-1,-1,-1):
            if dp[k][jj]>=0 and k+wv[i][0]-w0<=wp-1:
                dp[k+wv[i][0]-w0][jj+1]=max(dp[k][jj]+wv[i][1],dp[k+wv[i][0]-w0][jj+1])
for i in range(1,n+1):
    wp=w-w0*i
    if wp<0:
        continue
    elif wp>=3*i:
        ans=max(ans,sum(v[:i]))
    else:
        for j in range(i+1):
            for k in range(wp+1):
                ans=max(dp[k][j],ans)
print(ans)

Submission status: Accepted

Solution code:
n, w_max = map(int, input().split())
W, V = [], []
Diff_zero = []
Diff_one = []
Diff_two = []
Diff_three = []
for i in range(n):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
    diff = w - W[0]
    if diff == 0:
        Diff_zero.append(v)
    elif diff == 1:
        Diff_one.append(v)
    elif diff == 2:
        Diff_two.append(v)
    elif diff == 3:
        Diff_three.append(v)

Diff_zero = sorted(Diff_zero, reverse=True)
Diff_one = sorted(Diff_one, reverse=True)
Diff_two = sorted(Diff_two, reverse=True)
Diff_three = sorted(Diff_three, reverse=True)

Diff_zero_ruiseki = [0]
Diff_one_ruiseki = [0]
Diff_two_ruiseki = [0]
Diff_three_ruiseki = [0]

for i in range(len(Diff_zero)):
    Diff_zero_ruiseki.append(Diff_zero[i] + Diff_zero_ruiseki[-1])
for i in range(len(Diff_one)):
    Diff_one_ruiseki.append(Diff_one[i] + Diff_one_ruiseki[-1])
for i in range(len(Diff_two)):
    Diff_two_ruiseki.append(Diff_two[i] + Diff_two_ruiseki[-1])
for i in range(len(Diff_three)):
    Diff_three_ruiseki.append(Diff_three[i] + Diff_three_ruiseki[-1])

value_max = 0
w_zero = W[0]

for i in range(n+1):
    if i > len(Diff_zero):
        continue
    for j in range(n+1):
        if j > len(Diff_one):
            continue
        for k in range(n+1):
            if k > len(Diff_two):
                continue
            for l in range(n+1):
                if l > len(Diff_three):
                    continue
                if w_zero*i + (w_zero+1)*j + (w_zero+2)*k + (w_zero+3)*l > w_max:
                    continue
                if i + j + k + l > n:
                    continue

                value = Diff_zero_ruiseki[i] + Diff_one_ruiseki[j] + Diff_two_ruiseki[k] + Diff_three_ruiseki[l]
                value_max = max(value, value_max)

print(value_max)