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
# hello worldと表示する
#float型を許すな
#numpyはpythonで
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, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,w=MI()
lis=[LI() for i in range(n)]
u=lis[0][0]
vals=[[] for i in range(4)]
for i in range(n):
    if lis[i][0]==u:
        vals[0].append(lis[i][1])
    elif lis[i][0]==u+1:
        vals[1].append(lis[i][1])
    elif lis[i][0]==u+2:
        vals[2].append(lis[i][1])
    else:
        vals[3].append(lis[i][1])
#print(vals)
for i in range(4):
    vals[i].sort(reverse=True)
    vals[i]=list(accumulate(vals[i]))
    vals[i]=[0]+vals[i]
mx=0
#print(vals)
for i in range(len(vals[0])):
    for j in range(len(vals[1])):
        for k in range(len(vals[2])):
            for l in range(len(vals[3])):
                if u*i+(u+1)*j+(u+2)*k+(u+3)*l>w:
                    continue
                V=vals[0][i]+vals[1][j]+vals[2][k]+vals[3][l]
                if V>mx:
                    mx=V
print(mx)

Submission status: Accepted

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

max1 = w // wv[0][0]
min1 = w // (wv[0][0] + 3)
seq = list(range(n))
ans = 0

w_min = wv[0][0]
w_list = [[] for _ in range(4)]

for wa,va in wv:
    w_list[wa-w_min].append(va)

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

for i in range(4):
    for j in range(len(w_list[i])-1):
        w_list[i][j+1] += w_list[i][j]

for i in range(min1, max1+1):
    for w1 in range(i+1):
        for w2 in range(i-w1+1):
            for w3 in range(i-w1-w2+1):
                w4 = i - w1 - w2 - w3
                if w1 * w_min + w2 * (w_min+1) + w3 * (w_min+2) + w4 * (w_min+3) <= w:
                    if len(w_list[0]) >= w1 and len(w_list[1]) >= w2 and len(w_list[2]) >= w3 and len(w_list[3]) >= w4:
                        tmp = 0
                        if w1 >= 1:
                            tmp += w_list[0][w1-1]
                        if w2 >= 1:
                            tmp += w_list[1][w2-1]
                        if w3 >= 1:
                            tmp += w_list[2][w3-1]
                        if w4 >= 1:
                            tmp += w_list[3][w4-1]
                        ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    WV = [[int(x) for x in input().split()] for _ in range(N)]

    weight = set()
    weight.add(0)
    weight.add(WV[0][0])
    for i in range(1, N + 1):
        for j in range(3 * i):
            weight.add(WV[0][0] * i + j)

    weight = sorted(list(weight))

    dp = defaultdict(int)

    for i in range(N):
        for j in weight[::-1]:
            if j >= WV[i][0]:
                dp[j] = max(dp[j], dp[j - WV[i][0]] + WV[i][1])

    ans = 0
    for i in weight:
        if i > W:
            break
        ans = max(ans, dp[i])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
w0 = wv[0][0]
wv.sort(key=lambda x: (x[0], -x[1]))
w1, w2, w3, w4 = [], [], [], []
for w, v in wv:
    if w == w0:
        w1.append(v)
    elif w == w0 + 1:
        w2.append(v)
    elif w == w0 + 2:
        w3.append(v)
    else:
        w4.append(v)
Sw1, Sw2, Sw3, Sw4 = [0], [0], [0], [0]
S = 0
for v in w1:
    S += v
    Sw1.append(S)
S = 0
for v in w2:
    S += v
    Sw2.append(S)
S = 0
for v in w3:
    S += v
    Sw3.append(S)
S = 0
for v in w4:
    S += v
    Sw4.append(S)
l1, l2, l3, l4 = len(w1), len(w2), len(w3), len(w4)
V = 0
v = 0
for i in range(l1 + 1):
    if w0 * i > W:
        break
    for j in range(l2 + 1):
        if w0 * i + (w0 + 1) * j > W:
            break
        for k in range(l3 + 1):
            if w0 * i + (w0 + 1) * j + (w0 + 2) * k > W:
                break
            for l in range(l4 + 1):
                if w0 * i + (w0 + 1) * j + (w0 + 2) * k + (w0 + 3) * l > W:
                    break
                v = Sw1[i] + Sw2[j] + Sw3[k] + Sw4[l]
                V = max(V, v)
print(V)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N,W = map(int,readline().split())
goods = [tuple(map(int,readline().split())) for i in range(N)]

from collections import defaultdict

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

for (w,v) in goods:
    dnew = defaultdict(int)
    for key,value in d.items():
        dnew[key] = value
    for key,value in d.items():
        dnew[key+w] = max(dnew[key+w],d[key]+v)
    d = dnew
ans = 0
for k,v in d.items():
    if k <= W:
        ans = max(ans,v)
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, great_W = getNM()
query = [getList() for i in range(N)]
wei = []
val = []
for i in range(N):
    w, v = query[i]
    wei.append(w)
    val.append(v)

# 下限の数字て引く（あとで足し合わせた数 * wei_minを使う）
wei_min = min(wei)
for i in range(N):
    wei[i] -= wei_min

def part_sum_5(n, k, limit, wei, val):
    dp = [[[0] * (limit + 1) for i in range(k + 1)] for i in range(n + 1)]

    # 足し合わせN個でvalができる
    for i in range(1, n + 1):
        for j in range(1, k + 1):
            for l in range(limit + 1):
                dp[i][j][l] = dp[i - 1][j][l]
                if l - wei[i - 1] >= 0:
                    dp[i][j][l] = max(dp[i - 1][j][l], dp[i - 1][j - 1][l - wei[i - 1]] + val[i - 1])

    res = 0
    for i in range(n + 1):
        for j in range(limit + 1):
            if i * wei_min <= (great_W - j):
                res = max(res, dp[N][i][j])

    return res

print(part_sum_5(N, N, 301, wei, val))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, W = getNM()
query = [getList() for i in range(N)]
wei = []
val = []
for i in range(N):
    w, v = query[i]
    wei.append(w)
    val.append(v)

wei_min = min(wei)
for i in range(N):
    wei[i] -= wei_min

def part_sum_5(n, k, limit, wei, val):
    dp = [[[0] * (limit + 1) for i in range(k + 1)] for i in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, k + 1):
            for l in range(limit + 1):
                dp[i][j][l] = dp[i - 1][j][l]
                if l - wei[i - 1] >= 0:
                    dp[i][j][l] = max(dp[i - 1][j][l], dp[i - 1][j - 1][l - wei[i - 1]] + val[i - 1])

    res = 0
    for i in range(n + 1):
        for j in range(limit + 1):
            if i * wei_min <= (W - j):
                res = max(res, dp[N][i][j])

    return res

print(part_sum_5(N, N, 301, wei, val))

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    n, w = map(int, input().split())
    items = [list(map(int, input().split())) for _ in range(n)]
    DP = defaultdict(int)
    DP[0] = 0
    for weight, value in items:
        exists = list(DP.items())
        for key, total in exists:
            new_key = key + weight
            if new_key > w:
                continue
            new_total = total + value
            if DP[new_key] < new_total:
                DP[new_key] = new_total

    print(max(DP.values()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    n, w = map(int, input().split())
    items = [list(map(int, input().split())) for _ in range(n)]
    DP = defaultdict(int)
    DP[0] = 0
    for weight, value in items:
        exists = list(DP.items())
        for key, total in exists:
            new_key = key + weight
            new_total = total + value
            if DP[new_key] < new_total:
                DP[new_key] = new_total

    candidates = [0]
    for weight, value in sorted(DP.items()):
        if weight > w:
            break
        candidates.append(value)

    print(max(candidates))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
w=[0 for i in range(n)]
v=[[] for i in range(4)]
dp=[[0] for i in range(4)]
for i in range(n):
  w[i],vi=map(int,input().split())
  v[w[i]-w[0]].append(vi)
for i in range(4):
  v[i].sort(reverse=True)
  for j in v[i]:
    dp[i].append(dp[i][-1]+j)
def dfs(i,cost):
  if cost>W:
    return -10**10
  elif i==4:
    return 0
  else:
    val=0
    for j in range(len(dp[i])):
      val=max(val,dp[i][j]+dfs(i+1,cost+j*(w[0]+i)))
    return val
print(dfs(0,0))

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
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

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,W = IL()
dic = DD(list)

w0,v = IL()
heapq.heappush(dic[w0],-v)
for _ in range(N-1):
  w,v = IL()
  heapq.heappush(dic[w],-v)

DIC = DD(list)
for i in range(4):
  DIC[w0+i] = [0]
  while dic[w0+i]:
    DIC[w0+i].append(DIC[w0+i][-1]-heapq.heappop(dic[w0+i]))

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def resolve():
    N, W = list(map(int, input().split()))
    WV = [list(map(int, input().split())) for _ in range(N)]
    wbase = WV[0][0]
    d = {
        wbase: [0],
        wbase+1: [0],
        wbase+2: [0],
        wbase+3: [0],
    }
    for w, v in WV:
        d[w].append(v)
    for v in d.values():
        v.sort(reverse=True)
    
    accs = {}
    for i in range(4):
        accs[wbase+i] = [0]
        for j in range(len(d[wbase+i])):
            accs[wbase+i].append(accs[wbase+i][j]+d[wbase+i][j])
    
    res = 0
    for i in range(len(d[wbase])):
        for j in range(len(d[wbase+1])):
            for k in range(len(d[wbase+2])):
                for l in range(len(d[wbase+3])):
                    if i*wbase+j*(wbase+1)+k*(wbase+2)+l*(wbase+3) <= W:
                        res = max(res, accs[wbase][i]+accs[wbase+1][j]+accs[wbase+2][k]+accs[wbase+3][l])
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

dp = [[[0 for k in range(N * 3 + 1)] for j in range(N + 1)] for i in range(N + 1)]

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

res = 0

for i in range(N + 1):
    for j in range(N + 1):
        for k in range(3 * N + 1):
            if w0 * j + k <= W:
                res = max(res, dp[i][j][k])

print(res)

Submission status: Accepted

Solution code:
n,W = map(int,input().split())
lst = [[0]*(n+1) for _ in range(4)]
for i in range(n):
    w,v = map(int,input().split())
    if i == 0: x = w
    lst[w-x].append(v)
for i in range(4):
    lst[i].sort(reverse=True)
    for j in range(n): lst[i][j+1] += lst[i][j]
ans = 0
for a in range(n+1):
    for b in range(n+1-a):
        for c in range(n+1-a-b):
            if x*a+(x+1)*b+(x+2)*c > W: continue
            d = max((W-x*a-(x+1)*b-(x+2)*c)//(x+3),0)
            sumv = 0
            for i,j in enumerate((a,b,c,d)):
                if j == 0: continue
                sumv += lst[i][j-1]
            ans = max(sumv,ans)
print(ans)

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
from collections import Counter
w0=wv[0][0]
d={w0:[0],w0+1:[0],w0+2:[0],w0+3:[0],}
for w,v in wv:
  d[w].append(v)
for i in range(4):
  d[w0+i].sort(reverse=True)
sd={}
for i in range(4):
  tmp=0
  sd[w0+i]=[0]
  for v in d[w0+i]:
    tmp+=v
    sd[w0+i].append(tmp)
ans=0
for i in range(len(d[w0])):
  for j in range(len(d[w0+1])):
    for k in range(len(d[w0+2])):
      for l in range(len(d[w0+3])):
        if w0*i+(w0+1)*j+(w0+2)*k+(w0+3)*l<=W:
          ans=max(ans,sd[w0][i]+sd[w0+1][j]+sd[w0+2][k]+sd[w0+3][l])
print(ans)

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
wv=[list(map(int,input().split()))]
w0=wv[0][0]-1
wv[0][0]=1
# すべてのwからw0を引く
for _ in range(n-1):
  w,v=list(map(int,input().split()))
  wv.append([w-w0,v])
import numpy as np
dp=np.full((n+1,401),0,int)
# dp[k][w]:k個で重さwでの最大価値
dp[0]=0
for w,v in wv:
  for i in range(n):
    dp[n-i][w:]=np.maximum(dp[n-i][w:],dp[n-i-1][:-w]+v)
ans=0
for i in range(1,n+1):
  if W-i*w0<=0:break
  ans=max(ans,dp[i][min(W-i*w0,400)])
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, w = map(int, input().split())
    w1, v1 = map(int, input().split())
    values = [[] for _ in range(4)]
    values[0].append(v1)
    for _ in range(n - 1):
        wi, vi = map(int, input().split())
        values[wi - w1].append(vi)
    for i in range(4):
        values[i].sort(reverse=True)
    prefix = [[0] for _ in range(4)]
    for i in range(4):
        for j in range(len(values[i])):
            prefix[i].append(prefix[i][-1] + values[i][j])
    max_ans = 0
    tot_val = [0] * 4
    tot_weights = [0] * 4
    for i in range(min(len(values[0]), w // w1) + 1):
        tot_val[0] = prefix[0][i]
        tot_weights[0] = w1 * i
        for j in range(min(len(values[1]), w // (w1 + 1)) + 1):
            tot_val[1] = tot_val[0] + prefix[1][j]
            tot_weights[1] = tot_weights[0] + (w1 + 1) * j
            if tot_weights[1] > w:
                break
            for k in range(min(len(values[2]), w // (w1 + 2)) + 1):
                tot_val[2] = tot_val[1] + prefix[2][k]
                tot_weights[2] = tot_weights[1] + k * (w1 + 2)
                if tot_weights[2] > w:
                    break
                diff = w - tot_weights[2]
                min_select = min(diff // (w1 + 3), len(values[3]))
                tot_val[3] = tot_val[2] + prefix[3][min_select]
                tot_weights[3] = tot_weights[2] + min_select * (w1 + 3)
                max_ans = max(max_ans, tot_val[3])
    print(max_ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n,w=map(int,input().split())
knap=[[] for i in range(4)]
w0,v=map(int,input().split())
knap[0].append(v)
for i in range(n-1):
    W,v=map(int,input().split())
    knap[W-w0].append(v)
for i in range(4):
    knap[i].sort(reverse=1)
    knap[i]=[0]+knap[i]
for i in range(4):
    for j in range(1,len(knap[i])):
        knap[i][j]+=knap[i][j-1]
ans=0
for a in range(len(knap[0])):
    for b in range(len(knap[1])):
        for c in range(len(knap[2])):
            for d in range(len(knap[3])):
                if w0*a+(w0+1)*b+(w0+2)*c+(w0+3)*d<=w:
                    ans=max(ans,knap[0][a]+knap[1][b]+knap[2][c]+knap[3][d])
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    l = []
    w, v = map(int, input().split())
    ww = w
    dp = [[[0] * (3*N) for _ in range(N+1) ]for _ in range(N)]
    dp[0][1][0] = v
    l.append((0, v))
    for _ in range(N-1):
        w, v = map(int, input().split())
        l.append((w-ww, v))
    if W < ww:
        return 0
    for i in range(1, N):
        w, v = l[i]
        for j in range(1, N+1):
            for k in range(w):
                dp[i][j][k] = dp[i-1][j][k]
            for k in range(w, 3*N):
                dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k-w] + v)
    r = 0
    for i in range(N+1):
        wt = W - i * ww
        if wt < 0:
            break
        r = max(r, max(dp[-1][i][:wt+1]))
    return r
print(main())

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    WV = [tuple(map(int, input().split())) for _ in range(N)]
    cur = {0: 0}
    for w, v in WV:
        keys = sorted(cur.keys(), reverse=True)
        for k in keys:
            if k + w > W:
                continue
            cur[k + w] = max(cur[k] + v, cur.get(k + w, 0))
    return max(cur.values())

print(main())

Submission status: Accepted

Solution code:
from itertools import accumulate

N, W = map(int, input().split())
wv = {}
w1 = 0
for i in range(N):
  w, v = map(int, input().split())
  if i == 0:
    w1 = w
  if w in wv:
    wv[w].append(v)
  else:
    wv[w] = [v]

for w in wv:
  wv[w].sort(reverse=True)
  wv[w] = [0] + list(accumulate(wv[w]))

w2 = w1+1; w3 = w1+2; w4 = w1+3
for w in [w1, w1+1, w1+2, w1+3]:
  if w not in wv:
    wv[w] = [0]

ans = 0
for n1 in range(len(wv[w1])):
  for n2 in range(len(wv[w2])):
    for n3 in range(len(wv[w3])):
      for n4 in range(len(wv[w4])):
        w = w1*n1 + w2*n2 + w3*n3 + w4*n4
        if w <= W:
          ans = max(ans, wv[w1][n1]+wv[w2][n2]+wv[w3][n3]+wv[w4][n4])

print(ans)

Submission status: Accepted

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

w_to_idx = {0:0}
idx_to_w = {0:0}
idx_W = 0
def calc():
  global w_to_idx, idx_to_w, idx_W
  idx = 1
  w_max = 0
  for i in range(1, N+1):
    w = w1*i
    for j in range(3*i + 1):
      ww = w + j
      if ww in w_to_idx:
        continue
      w_to_idx[ww] = idx
      idx_to_w[idx] = ww
      if w_max < ww <= W:
        w_max = ww
        idx_W = idx
      idx += 1

calc()
n = len(w_to_idx)
dp = [[0]*n for i in range(N+1)]
for i, (w, v) in enumerate(wv, 1):
  for j in range(n):
    dp[i][j] = dp[i-1][j]
    ww = idx_to_w[j]
    if ww >= w and ww-w in w_to_idx:
      jj = w_to_idx[ww - w]
      dp[i][j] = max(dp[i][j], dp[i-1][jj] + v)

print(max(dp[-1][:idx_W+1]))

Submission status: Accepted

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

items = [[] for _ in range(4)]
w1, v = [int(_) for _ in input().split()]
items[0].append(v)

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

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

S = []
for i in range(4):
    l = len(items[i])
    s = [0] * (l + 1)
    for j in range(l):
        s[j + 1] = items[i][j] + s[j]
    S.append(s)

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

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
ws, vs = [], []
for i in range(n):
  wi, vi = map(int, input().split())
  ws.append(wi)
  vs.append(vi)
dp = [[[0] * (3 * i + 1) for i in range(n + 1)] for j in range(n + 1)]
for i in range(n):
  for j in range(n + 1):
    for k in range(3 * j + 1):
      dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k])
      if j < n:
        dp[i + 1][j + 1][k + ws[i] - ws[0]] = max(dp[i + 1][j + 1][k + ws[i] - ws[0]],
                                                  dp[i][j][k] + vs[i])
ans = 0
for i in range(n + 1):
  for j in range(3 * i + 1):
    if ws[0] * i + j <= w:
      ans = max(ans, dp[n][i][j])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N, W = list(map(int, input().split(' ')))
    items, cumsums = defaultdict(list), defaultdict(list)
    w_0 = 0
    for i in range(N):
        w, v = list(map(int, input().split(' ')))
        if i == 0:
            w_0 = w
        items[w].append(v)
    for w in items.keys():
        items[w].sort(reverse=True)
        cumsum_w, cumsum_v = 0, 0
        for v in items[w]:
            cumsum_w += w
            cumsum_v += v
            # w - w_0 is in [0, 1, 2, 3]
            cumsums[w - w_0].append((cumsum_w, cumsum_v))

    def dfs(cur, rest_w):
        if cur == 0:
            max_v = 0
            for cumsum_w, cumsum_v in cumsums[cur]:
                if cumsum_w <= rest_w:
                    max_v = cumsum_v
            return max_v
        else:
            ret = dfs(cur - 1, rest_w)
            for cumsum_w, cumsum_v in cumsums[cur]:
                if rest_w >= cumsum_w:
                    ret = max([ret, cumsum_v + dfs(cur - 1, rest_w - cumsum_w)])
            return ret

    print(dfs(3, W))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
data = tuple(tuple(map(int, input().split())) for _ in range(N))
d = {0: 0}
for n in range(N):
    weight, value = data[n]
    for w, now in d.copy().items():
        if w + weight <= W:
            d[w + weight] = max(d.get(w + weight, 0), now + value)
print(max(d.values()))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
data = tuple(tuple(map(int, input().split())) for _ in range(N))
table = [dict() for _ in range(N + 1)]
table[0][0] = 0
for n in range(N):
    weight, value = data[n]
    for w, now in table[n].items():
        table[n + 1][w] = max(table[n + 1].get(w, 0), now)
        if w + weight <= W:
            table[n + 1][w + weight] = max(table[n + 1].get(w + weight, 0), now + value)
print(max(table[N].values()))

Submission status: Accepted

Solution code:
from itertools import product

N, W = map(int,input().split())
L = [[] for _ in range(4)]
w, v = map(int,input().split())
L[0].append(v)
for _ in range(N-1):
    tmp_w, tmp_v = map(int,input().split())
    L[tmp_w - w].append(tmp_v)

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

for i in range(4):
    for j in range(len(L[i]) - 1):
        L[i][j+1] += L[i][j]
    L[i] = [0] + L[i]

ans = 0

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

print(ans)