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
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
N, W = map(int, input().split())
v = [[] for i in range(4)]
w1 = 0
for i in range(N):
    a, b = map(int, input().split())
    if i == 0:
        w1 = a
    v[a - w1].append(b)
for i in range(4):
    v[i].sort(reverse=True)
# print(v)
ans = 0
for i in range(N + 1):
    for j in range(N - i + 1):
        for k in range(N - i - j + 1):
            for l in range(N - i - j - k + 1):
                if w1 * (i + j + k + l) + j + 2 * k + 3 * l > W:
                    continue
                ans = max(ans, sum(v[0][:i]) + sum(v[1][:j]) + sum(v[2][:k]) + sum(v[3][:l]))
print(ans)

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    n, w = mi()
    L = [lmi() for _ in range(n)]
    w1 = L[0][0]
    if n * (w1 + 3) <= w:
        print(sum(map(lambda x: x[1], L)))
    elif n * w <= 10**6:
        # 普通の dp 戦略
        dp = [0 for _ in range(w+1)]
        for i in range(n):
            weight, value = L[i]
            for j in range(w, 0, -1):
                if j - weight >= 0:
                    dp[j] = max(dp[j], dp[j - weight] + value)
        print(dp[w])
    else:
        group_by_weight = [[] for _ in range(4)]
        for weight, value in L:
            group_by_weight[weight - w1].append(value)
        w1_0 = sorted(group_by_weight[0], reverse=True)
        w1_1 = sorted(group_by_weight[1], reverse=True)
        w1_2 = sorted(group_by_weight[2], reverse=True)
        w1_3 = sorted(group_by_weight[3], reverse=True)
        accum_0, accum_1, accum_2, accum_3 = map(lambda x: [0] + list(accumulate(x)), [w1_0, w1_1, w1_2, w1_3])
        ans = -1
        for i in range(len(w1_0)+1):
            for j in range(len(w1_1)+1):
                for k in range(len(w1_2)+1):
                    for l in range(len(w1_3)+1):
                        if (i+j+k+l)*w1 + j + 2*k + 3*l <= w:
                            ans = max(ans, accum_0[i] + accum_1[j] + accum_2[k] + accum_3[l])
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,W=map(int,input().split())
    w,v=[0]*N,[0]*N
    for i in range(N):
        w[i],v[i]=map(int,input().split())
    if w[0]>3*N:
        w0=w[0]
        W=min(W//w0*(3*N+1)+min(W%w0,3*N),(3*N+4)*N)
        for i in range(N):
            w[i]-=w0
            w[i]+=3*N+1
    dp=[[0]*(W+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])
            if j-w[i]>=0:
                dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
    print(dp[-1][-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

for i in stuff:
    i.sort(reverse=True)

ans = 0

for a in range(len(stuff[0])+1):
    for b in range(len(stuff[1])+1):
        for c in range(len(stuff[2])+1):
            for d in range(len(stuff[3])+1):

                if a*w1+b*(w1+1)+c*(w1+2)+d*(w1+3) <= W:
                    ans = max(ans,sum(stuff[0][:a])+sum(stuff[1][:b])+sum(stuff[2][:c])+sum(stuff[3][:d]))

print(ans)

Submission status: Accepted

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

memo = {}

def  nap(i, j):
    if i == N:
        return 0

    if (i, j) in memo:
        return memo[i, j]
    elif w_v[i][0] > j:
        temp = nap(i+1, j)
    else:
        temp = max(nap(i+1, j), nap(i+1, j-w_v[i][0]) + w_v[i][1])
    memo[i, j] = temp

    return memo[i, j]

print(nap(0, W))

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
wv = [[int(i) for i in input().split()] for j in range(n)]

wv.sort(key=lambda x:(x[0],-x[1]))
#print(wv)
#exit()
#wv.sort()
min_v = wv[0][0]
cnt = 0
num = [0]*4

for i in range(n):
    num[wv[i][0] - min_v] +=1
        
#dp = [[[0 for i in range(n)] for j in range(n)] for k in range(n)]

#print(wv)

t_num3 = [0]
tmp = 0
for i in range(num[3]):
    tmp += wv[n-num[3]+i][1]
    t_num3.append(tmp)

#print(t_num3)
#exit()

t_ans = 0
t_num0 = 0
ans = 0


for i in range(num[0]+1):
    if i != 0:
        t_num0 += wv[i-1][1]
    #print(t_ans,i)
    t_num1 = 0
    for j in range(num[1]+1):
        if j != 0:
            t_num1 += wv[num[0]+j-1][1]
        t_num2 = 0
        for k in range(num[2]+1):
            if k != 0:
                t_num2 += wv[num[0]+num[1]+k-1][1]
            ima_w = min_v*(i+j+k) + 1*j+2*k
            idx = (w - ima_w)//(min_v+3)
            if ima_w > w:
                break
            else:
                t_ans = t_num0+t_num1+t_num2 + t_num3[min(idx,num[3])]
        #print(t_ans)
            ans = max(t_ans,ans)

print(ans)

Submission status: Accepted

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

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

w2vlist=[]
for i in range(N):
  w,v=wvlist[i]
  w2vlist.append((w,w-w1,v))
#print(w2vlist)

dp=[[[0]*(3*N+1) for _ in range(N+1)] for _ in range(N+1)]
#print(dp)

for i in range(1,N+1):
  w,wd,v=w2vlist[i-1]
  for j in range(1,i+1):
    for k in range(3*N+1):
      dp[i][j][k]=dp[i-1][j][k]
      if k-wd>=0:
        dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-wd]+v)

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

Submission status: Accepted

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

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

w1,v1 = map(int,input().split())
for i in range(3*n+1):
    dp[0][0][i] = v1

for i in range(1,n):
    w,v = map(int,input().split())
    w -= w1
    for j in range(min(i+1,n)):
        for k in range(3*(j+1)+1):
            if j>0 and k>=w:
                dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k-w] + v)
            elif k>=w:
                dp[i][0][k] = max(dp[i-1][0][k], v)
            else:
                dp[i][j][k] = dp[i-1][j][k]

ans = 0
for i in range(n):
    for j in range(3*n+1):
        if w1*(i+1) + j>W: continue
        ans = max(ans,dp[-1][i][j])

print(ans)

Submission status: Accepted

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

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

w1,v1 = map(int,input().split())
for i in range(3*n+1):
    dp[0][0][i] = v1

for i in range(1,n):
    w,v = map(int,input().split())
    w -= w1
    for j in range(min(i+1,n)):
        for k in range(3*n+1):
            if j>0 and k>=w:
                dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k-w] + v)
            elif k>=w:
                dp[i][0][k] = max(dp[i-1][0][k], v)
            else:
                dp[i][j][k] = dp[i-1][j][k]

ans = 0
for i in range(n):
    for j in range(3*n+1):
        if w1*(i+1) + j>W: continue
        ans = max(ans,dp[-1][i][j])

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,W=map(int,input().split())

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

wv_sorted=sorted(wvdic.items())
#print(wv_sorted)

wvslist=[]
for i in range(len(wv_sorted)):
  slist=[0]
  vlist=sorted(wv_sorted[i][1],reverse=True)
  for v in vlist:
    slist.append(slist[-1]+v)
  wvslist.append((wv_sorted[i][0],slist))
if len(wvslist)<4:
  for _ in range(4-len(wvslist)):
    wvslist.append((-1,[0]))
#print(wvslist)

max_answer=0
for w1 in range(len(wvslist[0][1])):
  ww1=wvslist[0][0]*w1
  v1=wvslist[0][1][w1]
  for w2 in range(len(wvslist[1][1])):
    ww2=wvslist[1][0]*w2
    v2=wvslist[1][1][w2]
    for w3 in range(len(wvslist[2][1])):
      ww3=wvslist[2][0]*w3
      v3=wvslist[2][1][w3]
      for w4 in range(len(wvslist[3][1])):        
        ww4=wvslist[3][0]*w4
        v4=wvslist[3][1][w4]
        ww_total=ww1+ww2+ww3+ww4
        #print(ww1,ww2,ww3,ww4,v1,v2,v3,v4)
        if ww_total<=W:
          vtotal=v1+v2+v3+v4
          max_answer=max(max_answer,vtotal)
          
print(max_answer)

Submission status: Accepted

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

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

w2vlist=[]
for i in range(N):
  w,v=wvlist[i]
  w2vlist.append((w,w-w1,v))
#print(w2vlist)

dp=[[[0 for _ in range(3*N+1)] for _ in range(N+1)] for _ in range(N+1)]
#print(dp)

for i in range(1,N+1):
  w,wd,v=w2vlist[i-1]
  for j in range(N+1):
    for k in range(3*N+1):
      dp[i][j][k]=dp[i-1][j][k]
      if j>0 and k-wd>=0:
        dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-wd]+v)

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

Submission status: Accepted

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

# dp = [[float('inf') for _ in range(10**7+1)] for _ in range(n+1)]
# dp[0] = [0 for _ in range(10**7+1)]

dp_dict = {0: {0:0}} # w,v

'''
for i,pack in enumerate(pack_list):
    for value,weight in enumerate(dp[i]):
        dp[i+1][value] = min(dp[i][value],dp[i+1][value])
        dp[i+1][value+pack[1]] = min(dp[i+1][value+pack[1]],dp[i][value]+pack[0])

for i,num in enumerate(dp[-1][::-1]):
    if num <= w:
        print(10**7-i)'''

for i,pack in enumerate(pack_list):
    i += 1
    if i not in dp_dict:
        dp_dict[i] = {}
    for weight,v in dp_dict[i-1].items():
        if weight not in dp_dict[i]:
            dp_dict[i][weight] = v
        else:
            dp_dict[i][weight] = max(dp_dict[i][weight],v)
        if weight+pack[0] <= w:
            if weight+pack[0] not in dp_dict[i]:
                dp_dict[i][weight+pack[0]] = v+pack[1]
            else:
                dp_dict[i][weight+pack[0]] = max(dp_dict[i][weight+pack[0]],v+pack[1])

target = dp_dict[n]
max_num = 0

for k,v in target.items():
    if k <= w:
        max_num = max(max_num,v)

print(max_num)

Submission status: Accepted

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

w0 = X[0][0]
ctr = [[] for _ in range(4)]
for w, v in X:
    ctr[w - w0].append(v)

for n in range(4):
    values = sorted(ctr[n], reverse=True)
    s = [0] * (len(values) + 1)
    for i in range(len(values)):
        s[i + 1] = s[i] + values[i]
    ctr[n] = s

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
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)

w1=[0]+w1
w1=list(accumulate(w1))
w2=[0]+w2
w2=list(accumulate(w2))
w3=[0]+w3
w3=list(accumulate(w3))
w4=[0]+w4
w4=list(accumulate(w4))

#print(w1,w2,w3,w4)
#print(len(w1),len(w2),len(w3),len(w4))

ans=0
for a in range(len(w1)):
    for b in range(len(w2)):
        for c in range(len(w3)):
            for d in range(len(w4)):
                #print(a,b,c,d)
                wei=w*a+(w+1)*b+(w+2)*c+(w+3)*d
                val=w1[a]+w2[b]+w3[c]+w4[d]
                #print(wei,val)
                if wei<=W:
                    ans=max(val,ans)

print(ans)

Submission status: Accepted

Solution code:


def submit():
    n, w = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(n)]
    
    if items[0][0] > w:
        print(0) # 1個も選べない
        return

    if sum([e[0] for e in items]) <=  w:
        print(sum([e[1] for e in items])) # 全部選べる
        return

    # 以降、必ず1個は選ぶ
    # かつbase_weight <= W < all_weight
    base_weight = items[0][0]
    
    # dp[i][j][k] : i番目までのアイテムのうち、j個を選んだ時、weight kで最大価値
    # weightはbase_weightからの差分をカウントする
    # dp[i + 1][j][k] = 
    #   dp[i][j][k], dp[i][j - 1][k - (w - base_weight)]
    # j * base_weight + k <= wの範囲で計算する
    
    dp = [[[0 for _ in range(3 * n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        rw = items[i - 1][0] - base_weight
        v = items[i - 1][1]
        for j in range(i + 1):
            for k in range(3 * n + 1):
                if j * base_weight + k <= w:
                    if j - 1 >= 0 and k - rw >= 0:
                        dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][k - rw] + v)
                    else:
                        dp[i][j][k] = dp[i - 1][j][k]
                else:
                    break

    ans = 0
    for j in range(n + 1):
        for k in range(3 * n + 1):
            ans = max(ans, dp[n][j][k])
    print(ans)

submit()

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product
from collections import  defaultdict as dd
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
wi = wv[0][0]
vi = wv[0][1]
dic = dd(list)
dic_cumsum = dd(list)
for w,v in wv:
    dic[w].append(v)

for k,v in dic.items():
    tmp = sorted(v, reverse=True)
    dic_cumsum[k] = [0] + list(np.zeros((N + 1), dtype=np.int64))
    dic_cumsum[k][1:] = list(np.cumsum(tmp, dtype=np.int64))
for i in range(1,4):
    if wi+i not in dic_cumsum.keys():
        dic_cumsum[wi+i] = [0]
        
n = [len(dic_cumsum[wi]), len(dic_cumsum[wi+1]), len(dic_cumsum[wi+2]), len(dic_cumsum[wi+3])]
m = [list(range(val)) for val in n]
res = 0

for ls in product(m[0], m[1], m[2]):
    if sum(ls)*wi > W:
        continue
    tmp_value = 0
    tmp_weight = 0
    for i,k in enumerate(ls):
        tmp_value += dic_cumsum[wi + i][k]
        tmp_weight += k*(wi+i)
    if tmp_weight > W:
        continue
    # wi, wi+1, wi+2の個数が決まっているので、wi+3を何個取れるかはO(1)で求められる
    max_m3 = (W - tmp_weight) // (wi+3)
    m3 = min(max_m3, n[3]-1)
    tmp_value += dic_cumsum[wi+3][m3]
    if tmp_value > res:
        res = tmp_value
print(res)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(n)]
ss = s[0][0]
s.sort(key = lambda x : x[1], reverse = True)
t = [[] for _ in range(4)]
for u in s:
    t[u[0] - ss].append(u[1])
l1, l2, l3, l4 = len(t[0]) + 1, len(t[1]) + 1, len(t[2]) + 1, len(t[3]) + 1
a, b, = [0] * l1, [0] * l2
c, d, = [0] * l3, [0] * l4
for i in range(1, l1):
    a[i] = t[0][i - 1] + a[i - 1]
for i in range(1, l2):
    b[i] = t[1][i - 1] + b[i - 1]
for i in range(1, l3):
    c[i] = t[2][i - 1] + c[i - 1]
for i in range(1, l4):
    d[i] = t[3][i - 1] + d[i - 1]
ans = 0
for i in range(l1):
    for j in range(l2):
        for k in range(l3):
            for l in range(l4):
                if ss * (i + j + k + l) + (j + 2 * k + 3 * l) <= w:
                    ans = max(ans, a[i] + b[j] + c[k] + d[l])
print(ans)

Submission status: Accepted

Solution code:
# solution
import io

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

for k in wv.keys():
    wv[k].sort(reverse=True)

kw = list(wv.keys())
kw.sort()
l = [len(wv[k]) for k in kw]
l = l + (4 - len(l)) * [0]
# print(l)

ans = 0
for i in range(l[0] + 1):
    wi = kw[0] * i
    if W < wi:
        break
    vi = sum(wv[kw[0]][:i])
    if l[1] == 0:
        ans = max(ans, vi)
    for j in range(l[1] + 1):
        if 2 <= len(kw):
            wj = wi + kw[1] * j
            if W < wj:
                break
            vj = vi + sum(wv[kw[1]][:j])
            if l[2] == 0:
                ans = max(ans, vj)
            for k in range(l[2] + 1):
                if 3 <= len(kw):
                    wk = wj + kw[2] * k
                    if W < wk:
                        break
                    vk = vj + sum(wv[kw[2]][:k])
                    if l[3] == 0:
                        ans = max(ans, vk)
                    for m in range(l[3] + 1):
                        if 4 <= len(kw):
                            wm = wk + kw[3] * m
                            if W < wm:
                                break
                            vm = vk + sum(wv[kw[3]][:m])
                            ans = max(ans, vm)
print(ans)

Submission status: Accepted

Solution code:
n,W = map(int, input().split())
wv = []
w1,v1 = map(int, input().split())
wv.append([0,v1])
for i in range(n-1):
  w,v = map(int, input().split())
  w -= w1
  wv.append([w,v])
dp = [[[-(10 ** 18)] * 301 for j in range(n+1)] for i in range(n+1)]
dp[0][0][0] = 0
for key,(wi,vi) in enumerate(wv):
  for num in range(key+1):
    for weight in range(3 * key + 1):
      dp[key+1][num][weight] = max(dp[key+1][num][weight],dp[key][num][weight])
      dp[key+1][num+1][weight+wi] = max(dp[key+1][num+1][weight+wi],dp[key][num][weight] + vi)
ans = 0
for k,i in enumerate(dp):
  for num,v in enumerate(i[:k+1]):
    res = W - num * w1
    if res < 0:
      continue
    ans = max(ans,max(v[:min(res+1,301)]))
print(ans)

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
w0=0
w,v=[],[]
for i in range(n):
  ww,vv=map(int,input().split())
  if i==0:w0=ww
  w.append(ww-w0)
  v.append(vv)
dp=[[[0]*(n+1) for i in range(3*(n+1))] for i in range(n+1)]

for i in range(n):
  for j in range(3*n):
    for k in range(n):
      if j-w[i]>=0:
        dp[i][j][k+1]=dp[i-1][j-w[i]][k]+v[i]
      dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k])

ans=0
for i in range(n):
  for j in range(3*n):
    for k in range(n+1):
      if j+k*w0<=W:
        ans=max(dp[i][j][k],ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, W = map(int, input().split())
dd = defaultdict(list)
for i in range(n):
    weight, value = map(int, input().split())
    dd[weight].append(value)

a = min(dd.keys())
b, c, d = a+1, a+2, a+3
Vcum = defaultdict(lambda: [0])
for k in [a, b, c, d]:
    s = 0
    dd[k].sort(reverse=True)
    for val in dd[k]:
        s += val
        Vcum[k].append(s)

ans = 0
for w in range(len(dd[a])+1):
    for x in range(len(dd[b])+1):
        for y in range(len(dd[c])+1):
            if W < a*w+b*x+c*y:
                break
            z = min((W-a*w-b*x-c*y)//d, len(dd[d]))
            val = Vcum[a][w]+Vcum[b][x]+Vcum[c][y]+Vcum[d][z]
            ans = max(ans, val)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, W = map(int, input().split())
dd = defaultdict(list)
for i in range(n):
    weight, value = map(int, input().split())
    dd[weight].append(value)

a = min(dd.keys())
b, c, d = a+1, a+2, a+3
Vcum = defaultdict(lambda: [0])
for k in [a, b, c, d]:
    s = 0
    dd[k].sort(reverse=True)
    for val in dd[k]:
        s += val
        Vcum[k].append(s)

ans = 0
for w in range(len(dd[a])+1):
    for x in range(len(dd[b])+1):
        for y in range(len(dd[c])+1):
            for z in range(len(dd[d])+1):
                if W < a*w+b*x+c*y+d*z:
                    continue
                val = Vcum[a][w]+Vcum[b][x]+Vcum[c][y]+Vcum[d][z]
                ans = max(ans, val)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, W = map(int, input().split())
dd = defaultdict(list)
for i in range(n):
    weight, value = map(int, input().split())
    dd[weight].append(value)

for k in dd.keys():
    dd[k].sort(reverse=True)

a = min(dd.keys())
b, c, d = a+1, a+2, a+3
ans = 0
for w in range(len(dd[a])+1):
    for x in range(len(dd[b])+1):
        for y in range(len(dd[c])+1):
            for z in range(len(dd[d])+1):
                if W < a*w+b*x+c*y+d*z:
                    continue
                val = sum(dd[a][:w])+sum(dd[b][:x]) + \
                    sum(dd[c][:y])+sum(dd[d][:z])
                ans = max(ans, val)
print(ans)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
weights, values = zip(*[tuple(map(int, input().split()))for _ in range(n)])
min_w = min(weights)-1
weights = [weight-min_w for weight in weights]
W_MAX = 4*200
dp = [[0]*(W_MAX+1) for _ in range(n+1)]
for i in range(1, n+1):
    for k in reversed(range(1, n+1)):
        for j in range(1, W_MAX+1):
            if j-weights[i-1] < 0:
                continue
            dp[k][j] = max(dp[k][j], dp[k-1][j-weights[i-1]]+values[i-1])

ans = 0
for k in range(n+1):
    w_max = min(w-k*min_w, W_MAX)
    if w_max < 0:
        continue
    ans = max(ans, dp[k][w_max])
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
v1 = []
v2 = []
v3 = []
v4 = []
w1,v = map(int,input().split())
v1.append(v)
for i in range(N-1):
    w,v = map(int,input().split())
    if w == w1:
        v1.append(v)
    elif w == w1 + 1:
        v2.append(v)
    elif w == w1 + 2:
        v3.append(v)
    elif w == w1 + 3:
        v4.append(v)
v1.sort(reverse=True)
v2.sort(reverse=True)
v3.sort(reverse=True)
v4.sort(reverse=True)

l1 = len(v1)
l2 = len(v2)
l3 = len(v3)
l4 = len(v4)
ans = 0
for i in range(l1+1):
    for j in range(l2+1):
        for k in range(l3+1):
            for l in range(l4+1):

                if i*w1 + j*(w1+1) + k*(w1+2) + l*(w1+3) <= W:
                    temp = sum(v1[:i]) + sum(v2[:j]) + sum(v3[:k]) + sum(v4[:l])
                    ans = max(ans,temp)
print(ans)

Submission status: Accepted

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

w1 = item[0][0]
V = [[] for _ in range(4)]
for w, v in item:
    V[w - w1].append(v)
for i in range(4):
    V[i].sort(reverse=True)

cnt = [0] * 4
for i in range(4):
    cnt[i] = len(V[i])

ans = 0
for i in range(cnt[0] + 1):
    S0 = sum(V[0][:i])
    W0 = i * w1
    for j in range(cnt[1] + 1):
        S1 = sum(V[1][:j])
        W1 = j * (w1 + 1)
        for k in range(cnt[2] + 1):
            S2 = sum(V[2][:k])
            W2 = k * (w1 + 2)
            for l in range(cnt[3] + 1):
                S3 = sum(V[3][:l])
                W3 = l * (w1 + 3)
                if W0 + W1 + W2 + W3 <= W:
                    ans = max(ans, S0 + S1 + S2 + S3)

print(ans)