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, deque
# import math
# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 1000000007

def solve():
    N, W = getList()
    MI = 100
    MJ = 300
    sina = []
    w, v = getList()
    w1 = w
    v1 = v
    # sina.append((w ,v))
    for i in range(N-1):
        w, v = getList()
        sina.append((w - w1, v))

    dp = [-1 for i in range(MI*MJ+MI+MJ)]
    dp[0] = 0
    dp[MJ] = v1
    for w, v in sina:
        # print(w,v)
        nxt = [-1 for i in range(MI*MJ+MI+MJ)]
        for i in range(MI):
            for j in range(MJ):
                cur = dp[i*MJ + j]
                if cur != -1:
                    if nxt[i * MJ + j] < cur:
                        nxt[i * MJ + j] = cur
                    # print(cur)
                    # print(nxt[(i+1) * MJ + j + w])
                    if nxt[(i+1) * MJ + j + w] < cur + v:
                        nxt[(i + 1) * MJ + j + w] = cur + v
                        # print("update")

        dp = nxt
        # for i in range(MI):
        #     print(dp[i * MJ:i * MJ + MJ - 1])

    ans = 0
    for i in range(MI):
        for j in range(MJ):
            # print(i, j, dp[i * MJ + j])
            if w1 * i + j <= W:

                if dp[i*MJ + j] > ans:
                    # print(dp[i+MJ + j])
                    ans = dp[i * MJ + j]

    print(ans)






def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, W, items):
    w1 = items[0][0]
    dp = [[[0] * (3 * N + 1) for _ in range(N + 1)] for __ in range(N + 1)]
    dp[0][0][0] = 0
    for i in range(N):
        iw, iv = items[i]
        iw -= w1
        for j in range(N + 1):
            for w in range(3 * N + 1):
                if j * w1 + w > W: break
                if w >= iw and j >= 1:
                    dp[i + 1][j][w] = max(dp[i][j][w], dp[i][j - 1][w - iw] + iv)
                else:
                    dp[i + 1][j][w] = dp[i][j][w]
    ans = 0
    for j in range(N + 1):
        for w in range(3 * N + 1):
            ans = max(ans, dp[N][j][w])
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, W, items)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,W=map(int, input().split())
Ws=[]
Vs=[]
for i in range(N):
    w,v=map(int, input().split())
    Ws.append(w)
    Vs.append(v)

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


for i in range(N):
    w=Ws[i]
    v=Vs[i]
    A=list( D.items())
    for dw,dv in A:
        #print(dw,dv)
        if dw+w<=W:
            D[dw+w]=max(D[dw+w], v+dv)
#print(Ws,Vs)
#print(D)
print(max(D.values()))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import itertools
n,w = map(int,input().split())
c = []
s = 0
for i in range(n):
  a,v = map(int,input().split())
  s += a
  c.append((a,v))
  
r = c[0][0]
L = min(100,w//r)
m = s-r*n+1
dp = [[[-float('inf')]*m for i in range(L+1)] for i in range(n+1)]
for i in range(n):
  dp[i][0][0] = 0

for i in range(n):
  for j in range(L):
    for k in range(m):
      W,V = c[i]
      R = W-r
      if k-R >= 0 and r*(j+1)+k <= w:
        dp[i+1][j+1][k] = max(dp[i][j+1][k],dp[i][j][k-R]+V)
      else:
        dp[i+1][j+1][k] = dp[i][j+1][k]
        
print(max(0,max(list(itertools.chain.from_iterable(dp[n])))))

Submission status: Accepted

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

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)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

# a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



#22-

n,w= list(map(int, input().split()))
item = [[] for i in range(4)]
ww = 0
for i in range(n):
    temp = list(map(int, input().split()))
    if(i==0):
        ww = temp[0]
    item[temp[0]-ww].append(temp[1])
    
for i in range(4):
    item[i].sort()
    item[i].reverse()

#print(item)
ans = 0

sums = [[0],[0],[0],[0]]

for i in range(4):
    for j in rl(item[i]):
        sums[i].append(sums[i][-1] + item[i][j])
#print(sums)


for i1 in range(len(item[0])+1):
    for i2 in range(len(item[1])+1):
        for i3 in range(len(item[2])+1):
            for i4 in range(len(item[3])+1):
                wei = (i1+i2+i3+i4)*ww + i2 + i3*2 + i4*3
                if(wei<=w):
                    val = sums[0][i1] + sums[1][i2] + sums[2][i3] + sums[3][i4]
                    ans = max(ans,val)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from collections import Counter
from itertools import accumulate, product

N, W = inpl()
A = []
for _ in range(N):
    A.append(inpl())
B = [[] for _ in range(4)]
w1 = A[0][0]

for w, v in A:
    B[w-w1].append(v)

B = [sorted(b, reverse=True) for b in B]
C = [[0] + list(accumulate(b)) for b in B]

res = 0

for a, b, c, d in product(range(len(C[0])),
                          range(len(C[1])),
                          range(len(C[2])),
                          range(len(C[3]))):
    if w1*a + (w1+1)*b + (w1+2)*c + (w1+3)*d <= W:
        res = max(res, C[0][a] + C[1][b] + C[2][c] + C[3][d])
print(res)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import numpy as np

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    cumsum = dict()
    L = defaultdict(int)
    for i in range(4):
        w = w1 + i
        d[w].sort(reverse=True)
        c = np.cumsum(d[w])
        cumsum[w] = c
        L[i] = len(d[w])

    ans = 0
    for i in range(L[0] + 1):
        if i != 0:
            v1 = cumsum[w1][i - 1]
        else:
            v1 = 0
        for j in range(L[1] + 1):
            if j != 0:
                v2 = v1 + cumsum[w1 + 1][j - 1]
            else:
                v2 = v1
            for k in range(L[2] + 1):
                if k != 0:
                    v3 = v2 + cumsum[w1 + 2][k - 1]
                else:
                    v3 = v2
                for l in range(L[3] + 1):
                    w = w1 * i + (w1 + 1) * j + (w1 + 2) * k + (w1 + 3) * l
                    if w > W:
                        continue

                    if l != 0:
                        v4 = v3 + cumsum[w1 + 3][l - 1]
                    else:
                        v4 = v3

                    if v4 > ans:
                        ans = v4

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    from itertools import groupby, product
    base_w = w[0]
    v_list = [[] for _ in range(4)]
    for ww, vv in zip(w, v):
        v_list[ww-base_w].append(vv)
    v_list = [sorted(vv, reverse=True) for vv in v_list]
    acc_v = [[0] for _ in range(4)]
    for i, vv in enumerate(v_list):
        for vvv in vv:
            acc_v[i].append(acc_v[i][-1] + vvv)
    ans = 0
    for i, j, k, l in product(*[range(len(a)) for a in acc_v]):
        if i * base_w + j * (base_w + 1) + k * (base_w + 2)+ l * (base_w + 3) > W:
            continue
        ans = max(ans, acc_v[0][i] + acc_v[1][j] + acc_v[2][k] + acc_v[3][l])
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    print(solve(N, W, w, v))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
import sys

N, W = map(int, sys.stdin.readline().strip().split())

weights = []
for _ in range(N):
    w, v = map(int, sys.stdin.readline().strip().split())
    weights.append((w, v))

MAX_WEIGHTS = 4 * 101
# iまでのものj個を使ってw1を基準とした重さkの時の価値の最大値
dp = [[[-1 for _ in range(MAX_WEIGHTS)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 0

ans = 0
BASE = weights[0][0]
for i in range(N):
    for j in range(i+1):
        for k in range(MAX_WEIGHTS):
            if dp[i][j][k] < 0:
                continue
            w, v = weights[i]
            w -= BASE
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            ans = max(ans, dp[i+1][j][k])
            if k + w + (j+1) * BASE <= W and k + w < MAX_WEIGHTS:
                dp[i+1][j+1][k+w] = dp[i][j][k] + v
                ans = max(ans, dp[i+1][j+1][k+w])

print(ans)

Submission status: Accepted

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

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

wi,vi=map(int,input().split())
w1=wi
ws[w1-wi].append(vi)

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

for i in range(4):
    ws[i]=sorted(ws[i])[::-1]

ans=0
#print(ws)
for i in range(-1,len(ws[0])):
    sum_vi=0
    wi=0

    if(i!=-1):
        sum_vi=sum(ws[0][:i+1])
        wi=w1*(i+1)
    if(wi>w):
#        print("i:{0},wi:{1}".format(i,wi))
        break

    for j in range(-1,len(ws[1])):
        sum_vj=sum_vi
        wj=wi

        if(j!=-1):
            sum_vj=sum_vi+sum(ws[1][:j+1])
            wj=wi+(w1+1)*(j+1)
        if(wj>w):
#            print("i:{0},j:{1},wj:{2}".format(i,j,wj))
            break

        for k in range(-1,len(ws[2])):
            sum_vk=sum_vj
            wk=wj

            if(k!=-1):
                sum_vk=sum_vj+sum(ws[2][:k+1])
                wk=wj+(w1+2)*(k+1)
            if(wk>w):
#                print("i:{0},j:{1},k:{2},wk:{3}".format(i,j,k,wk))
                break

            w_rest=w-wk
            l=w_rest//(w1+3)
            sum_vl=sum_vk
            wl=wk
#            print(sum_vi,sum_vj,sum_vk,wi,wj,wk)
            if(l>len(ws[3])):
                sum_vl+=sum(ws[3])
                wl+=(w1+3)*len(ws[3])
            else:
                sum_vl+=sum(ws[3][:l])
                wl+=(w1+3)*l
#            print("i:{0},j:{1},k:{2},l:{3},wl:{4},w_rest:{5},sum_v:{6}".format(i,j,k,l,wl,w_rest,sum_vl))
            if(ans<sum_vl):
#                print(i,j,k,min(l,len(ws[3])),sum_vl)
                ans=sum_vl
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

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

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

N,W = MI()
WV = LI(N)

ls_w = mycol(WV,0)
ls_w = list(set(ls_w))
ls_w.sort()
if len(ls_w)==3:
    ls_w = [0] + ls_w
elif len(ls_w)==2:
    ls_w = [0,0] + ls_w
elif len(ls_w)==1:
    ls_w = [0,0,0] + ls_w
else:
    pass
# print(ls_w)

a = []
b = []
c = []
d = []
for i in range(N):
    w = WV[i][0]
    v = WV[i][1]
    ind = ls_w.index(w)
    if ind==0:
        a.append(v)
    elif ind==1:
        b.append(v)
    elif ind==2:
        c.append(v)
    elif ind==3:
        d.append(v)
    else:
        print("E")
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
d.sort(reverse=True)
# print("---")
# print(a)
# print(b)
# print(c)
# print(d)
# print("---")

M = -1*INF

for i in range(len(a)+1):
    for j in range(len(b)+1):
        for k in range(len(c)+1):
            for l in range(len(d)+1):
                w = i*ls_w[0] + j*ls_w[1] + k*ls_w[2] + l*ls_w[3]
                if w>W:
                    pass
                else:
                    v = sum(a[:i]) + sum(b[:j]) + sum(c[:k]) + sum(d[:l])
                    M = max(M,v)
print(M)

Submission status: Accepted

Solution code:
import collections
N, W = map(int, input().split())
wv = collections.defaultdict(list)
w = 0
for i in range(N):
    a, b = map(int, input().split())
    wv[a].append(b)
    if i == 0:
        w = a
s = [[0]*(len(wv[w+i])+1) for i in range(4)]

for i in range(4):
    wv[w + i].sort(reverse=True)
    for j, x in enumerate(wv[w + i]):
        s[i][j+1] = s[i][j] + x
ans = 0
L = len(wv[w+3])
for i in range(min(len(wv[w]), N)+1):
    tmp1 = s[0][i]
    weight1 = w * i
    if weight1 > W:
        break
    for j in range(min(len(wv[w+1])+1, N+1 - i)):

        tmp2 = tmp1 + s[1][j]
        weight2 = weight1 + (w+1)*j
        if weight2 > W:
            break
        for k in range(min(len(wv[w+2])+1, N+1 - i - j)):
            tmp3 = tmp2 + s[2][k]
            weight3 = weight2 + (w+2)*k
            if weight3 > W:
                break
            d = W - weight3

            ans = max(ans, tmp3 + s[3][min(L, d//(w+3))])
print(ans)

Submission status: Accepted

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

for w, v in wv:
    L[w-w0].append(v)

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

acc = [[0] for _ in range(4)]

for i in range(4):
    for j in range(len(L[i])):
        acc[i].append(acc[i][-1]+L[i][j])

ans = 0

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

print(ans)

Submission status: Accepted

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

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

w1,v1 = map(int,input().split())

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 w1*a + (w1+1)*b + (w1+2)*c + (w1+3)*d <= 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:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,W = LI()
    B = [[0,0]]+[LI() for _ in range(N)]

    k_min = max(1,W // (B[1][0] + 3))
    k_max = min(W // B[1][0],N)

    if B[1][0] <= 300: base = 0
    else: base = B[1][0] - 300
    for i in range(1,N+1): B[i][0] -= base

    ans = 0
    for k in range(k_min,k_max+1):
        w_sub = min(303 * k,W - k*base)
        dp = [[0] * (w_sub+1) for _ in range(N+1)]
        for i in range(1,N+1):
            for j in range(1,w_sub+1):
                if j - B[i][0] >= 0:
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-B[i][0]] + B[i][1])
                else:
                    dp[i][j] = dp[i-1][j]
        ans = max(ans,dp[-1][-1])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


def solve():
    dp = collections.defaultdict(lambda: -1)
    dp[0] = 0
    for i in range(N):
        wi, vi = items[i]
        ndp = collections.defaultdict(lambda: -1)
        for ws, vs in dp.items():
            if ws + wi <= W:
                ndp[ws + wi] = max(ndp[ws + wi], vs + vi)
        for wt, vt in ndp.items():
            dp[wt] = max(dp[wt], vt)
    return max(dp.values())


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    dd = defaultdict(int)
    dd[0] = 0
    for w, v in items:
        for tw, tv in list(dd.items()):
            if tw + w <= W:
                dd[tw + w] = max(tv + v, dd[tw + w])
    print(max(dd.values()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 全ての重さがw1,w1 + 1,w1 + 2,w1 + 3のいずれかである
# 共通の重さであるw1を引いた値、0,1,2,3で重さナップサック
# ただし、そこまでに使った物の数もdpで管理し、[数] * w1 + [0,1,2,3の重さ]がWを越えないようにDPする。
# 配列の長さは3 * N + 1(0の状態を管理するため+1)でOK

N,W = map(int,input().split())
items = [None] * N
items[0] = list(map(int,input().split()))
base = items[0][0]
items[0][0] = 0
for i in range(1,N):
  items[i] = list(map(int,input().split()))
  items[i][0] -= base

# dp[0,1,2,3の重さ(3 * N + 1)][商品数(N)] = 価値の最大値
dp = [[-1 for i in range(N + 1)] for j in range(3 * N + 1)]
# 重さ0で商品を一つも入れていない状態は価値0
dp[0][0] = 0
for i in range(len(items)):
  w = items[i][0]
  v = items[i][1]
  for j in range(len(dp)-1,-1,-1):
    # jは[重さ]
    for k in range(len(dp[j])-1,-1,-1):
      # kは商品の個数
      if dp[j][k] != -1:
        if j + w < len(dp) and k * base + j <= W:
          if dp[j + w][k + 1] < dp[j][k] + v:
            dp[j + w][k + 1] = dp[j][k] + v
            
ans = 0
for i in range(len(dp)):
  for j in range(len(dp[i])):
    if i + j * base <= W and ans < dp[i][j]:
      ans = dp[i][j]
      
print(ans)

Submission status: Accepted

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

from collections import defaultdict
vals = defaultdict(list)
for tmp in wv:
    w,v=tmp
    vals[w-w1].append(v)

v1=sorted(vals[0],reverse=True)
v2=sorted(vals[1],reverse=True)
v3=sorted(vals[2],reverse=True)
v4=sorted(vals[3],reverse=True)

ans=-1
for num1 in range(len(v1)+1):
    for num2 in range(len(v2)+1):
        for num3 in range(len(v3)+1):
            for num4 in range(len(v4)+1):
                sumw = num1*w1 + num2*(w1+1) + num3*(w1+2) + num4*(w1+3)
                if sumw <=weight:
                    sm = sum(v1[:num1]) + sum(v2[:num2]) +  sum(v3[:num3]) +  sum(v4[:num4])
                    ans=max(ans,sm)
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split(" "))
items = {i: [] for i in range(4)}
w1 = -1
for _ in range(N):
    w, v = map(int, input().split(" "))
    if w1 == -1:
        w1 = w
    items[w - w1].append(v)

for i in range(4):
    items[i].sort()
    items[i].append(0)
    items[i].reverse()
    for j in range(1, len(items[i])):
        items[i][j] += items[i][j - 1]

ans = 0
for i in range(len(items[3])):
    if i * (w1 + 3) > W:
        break
    for j in range(len(items[2])):
        if i * (w1 + 3) + j * (w1 + 2) > W:
            break
        for k in range(len(items[1])):
            if i * (w1 + 3) + j * (w1 + 2) + k * (w1 + 1) > W:
                break
            w_three = (W - i * (w1 + 3) - j * (w1 + 2) - k * (w1 + 1)) // w1
            w_three = min(len(items[0]) - 1, w_three)
            ans = max(items[3][i] + items[2][j] + items[1][k] + items[0][w_three], ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
A = [tuple(map(int, input().split())) for _ in [0]*N]
w0 = A[0][0]
A = [(w-w0, v) for w, v in A]

dp = [[0]*(3*N) for _ in [0]*(N+1)]
ans = 0
sumw = 0
for k, (w, v) in enumerate(A):
    for i in range(k, -1, -1):
        for j in range(sumw, -1, -1):
            if 0 <= i < N and 0 <= j+w < 3*N and (i+1)*w0+j+w <= W:
                dp[i+1][j+w] = max(dp[i][j]+v, dp[i+1][j+w])
    sumw += w

for d in dp:
    ans = max(ans, *d)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    ctr = [0] * 4
    goods = [[] for _ in range(4)]

    w1, v1 = map(int, input().split())
    ctr[0] += 1
    goods[0].append(v1)

    for _ in range(N - 1):
        wi, vi = map(int, input().split())
        wi -= w1
        ctr[wi] += 1
        goods[wi].append(vi)

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

    def accumulate(a):
        s = 0
        yield s
        for x in a:
            s += x
            yield s

    accs = [list(accumulate(goods_i)) for goods_i in goods]

    ans = -1
    for c0 in range(N + 1):
        if ctr[0] < c0: break
        if w1 * c0 > W: break

        v0 = accs[0][c0]
        for c1 in range(N - c0 + 1):
            if ctr[1] < c1: break
            if w1 * c0 + (w1 + 1) * c1 > W: break

            v1 = v0 + accs[1][c1]
            for c2 in range(N - c0 - c1 + 1):
                if ctr[2] < c2: break
                if w1 * c0 + (w1 + 1) * c1 + (w1 + 2) * c2 > W: break

                v2 = v1 + accs[2][c2]
                for c3 in range(N - c0 - c1 - c2 + 1):
                    if ctr[3] < c3: break
                    if w1 * c0 + (w1 + 1) * c1 + (w1 + 2) * c2 + (w1 + 3) * c3 > W: break
                    v3 = v2 + accs[3][c3]
                    ans = max(ans, v3)

    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    dd = defaultdict(int)
    dd[0] = 0
    for w, v in items:
        for tw, tv in list(dd.items()):
            if tw + w <= W:
                dd[tw + w] = max(tv + v, dd[tw + w])
    print(max(dd.values()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy

n, W = map(int, input().split())
product = [[0] for _ in range(4)]

w, v = map(int, input().split())
w_0 = w
product[0].append(v)
for i in range(n-1):
  w, v = map(int, input().split())
  product[w-w_0].append(v)

product[0].sort()
product[1].sort()
product[2].sort()
product[3].sort()

for i in range(len(product[0])-1):
  product[0][i+1] = product[0][i+1]+product[0][i]
for i in range(len(product[1])-1):
  product[1][i+1] = product[1][i+1]+product[1][i]
for i in range(len(product[2])-1):
  product[2][i+1] = product[2][i+1]+product[2][i]
for i in range(len(product[3])-1):
  product[3][i+1] = product[3][i+1]+product[3][i]

ans = 0
for a in range(len(product[0])):
  for b in range(len(product[1])):
    for c in range(len(product[2])):
      for d in range(len(product[3])):
        weight = w_0*(len(product[0])-a-1)+(w_0+1)*(len(product[1])-b-1)+(w_0+2)*(len(product[2])-c-1)+(w_0+3)*(len(product[3])-d-1)
        if weight > W:
          continue
        sub = 0
        sub += (product[0][len(product[0])-1]-product[0][a])
        sub += (product[1][len(product[1])-1]-product[1][b])
        sub += (product[2][len(product[2])-1]-product[2][c])
        sub += (product[3][len(product[3])-1]-product[3][d])
        if ans < sub:
          ans = sub
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin,setrecursionlimit

n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]

kijyun = li[0][0]

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

for i in li:
    omosa[i[0]-kijyun].append(i[1])

for i in range(len(omosa)):
    omosa[i].sort(reverse = True)

ma = 0

for i in range(len(omosa[0])+1):
    for j in range(len(omosa[1])+1):
        for k in range(len(omosa[2])+1):
            for l in range(len(omosa[3])+1):
                to_ka = omosa[0][:i]+omosa[1][:j]+omosa[2][:k]+omosa[3][:l]
                if i*kijyun+j*(kijyun+1)+k*(kijyun+2)+l*(kijyun+3) > w:
                    continue
                ma = max(ma,sum(to_ka))

print(ma)

Submission status: Accepted

Solution code:
from sys import stdin,setrecursionlimit

n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]

jw = li[0][0]
omosa = [[] for _ in range(4)]

for i in li:
    omosa[i[0]-jw].append(i[1])

for i in range(len(omosa)):
    omosa[i].sort(reverse = True)

saidai = n
ma = 0

for i in range(len(omosa[0])+1):
    for j in range(len(omosa[1])+1):
        for k in range(len(omosa[2])+1):
            for l in range(len(omosa[3])+1):
                to_ka = omosa[0][:i]+omosa[1][:j]+omosa[2][:k]+omosa[3][:l]
                if i*jw+j*(jw+1)+k*(jw+2)+l*(jw+3) > w:
                    continue
                ma = max(ma,sum(to_ka))

print(ma)

Submission status: Accepted

Solution code:
import itertools
N,W=map(int,input().split())
item=[[] for i in range(4)]
for i in range(N):
    w,v=map(int,input().split())
    if(i==0):
        base=w
        item[0].append(v)
    else:
        item[w-base].append(v)
for i in range(4):
    item[i].sort(reverse=True)
l1=len(item[0]);l2=len(item[1]);l3=len(item[2]);l4=len(item[3])
res=0
for x in itertools.product(range(l1+1),range(l2+1),range(l3+1),range(l4+1)):
    if(x[0]*base+x[1]*(base+1)+x[2]*(base+2)+x[3]*(base+3)>W):
        continue
    tmp=sum(item[0][:x[0]])+sum(item[1][:x[1]])+sum(item[2][:x[2]])+sum(item[3][:x[3]])
    res=max(res,tmp)
print(res)