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: Time Limit Exceeded

Solution code:
# coding: utf-8
import array, bisect, collections, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
 
 
def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}
 
 
def solve(N, W, w, v):
    dp = [[-1] * (N + 1) for __ in range(W + 1)]
    def throw(weight=W, num=0):
        if dp[weight][num] != -1:
            return dp[weight][num]
        
        if num == N:
            return 0
        elif weight < w[num]:
            res = throw(weight, num + 1)
        else:
            res = max(throw(weight, num + 1), throw(weight - w[num], num + 1) + v[num])
        
        dp[weight][num] = res
        return res
    
    ans = throw()
    return ans
    
 
def main():
    N, W = ILI()
    w, v = [], []
    for __ in range(N):
        x, y = ILI()
        w.append(x)
        v.append(y)
    print(solve(N, W, w, v))
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, W = map(int, raw_input().split())
w = []
v = []
dp = [[0]*n for _ in xrange(W+1)]
for _ in xrange(n):
    a, b = map(int, raw_input().split())
    w.append(a)
    v.append(b)
for i in xrange(n):
    dp[0][i] = 0
for _ in xrange(w[0], W+1):
    dp[_][0] = v[0]
for i in xrange(1, n):
    for j in xrange(1, W+1):
        k = j - w[i]
        if k < 0:
            x = 0
        else:
            x = dp[k][i-1] + v[i]
        if dp[j][i-1] > x:
           x = dp[j][i-1]
        dp[j][i] = x
        # for _ in xrange(W+1):
        #     print dp[_]
        # print ""
print dp[-1][-1]

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import array, bisect, collections, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
 
 
def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}
 
 
def solve(N, W, w, v):
    dp = [[-1] * (N + 1) for __ in range(W + 1)]
    def throw(weight=W, num=0):
        if dp[weight][num] != -1:
            return dp[weight][num]
        
        if num == N:
            return 0
        elif weight < w[num]:
            res = throw(weight, num + 1)
        else:
            res = max(throw(weight, num + 1), throw(weight - w[num], num + 1) + v[num])
        
        dp[weight][num] = res
        return res
    
    ans = throw()
    return ans
    
 
def main():
    N, W = ILI()
    w, v = [], []
    for __ in range(N):
        x, y = ILI()
        w.append(x)
        v.append(y)
    print(solve(N, W, w, v))
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
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())

def r(i, g):
    if i == N:
        return 0
    elif g < w[i]:
        return r(i + 1, g)
    else:
        return max(r(i + 1, g - w[i]) + v[i], r(i + 1, g))

print(r(0, W))

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

n, w = map(int, input().split())
vi = [[] for _ in range(4)]
wi0, vi0 = map(int, input().split())
vi[0].append(vi0)

for _ in range(n-1):
    wii, vii = map(int, input().split())
    vi[wii-wi0].append(vii)

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

ret = 0
for i in range(len(vi[3])):
    for j in range(len(vi[2])):
        for k in range(len(vi[1])):
            tw = i*(wi0+3)+j*(wi0+2)+k*(wi0+1)
            l = max(0,min(len(vi[0])-1,(w - tw)//wi0))
            tw += l*(wi0)
            if tw > w: continue
            tv = vi[3][i]+vi[2][j]+vi[1][k]+vi[0][l]
            ret = max(ret, tv)
print(ret)

Submission status: Accepted

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

WVs = [list(map(int, input().split())) for _ in range(N)]

memo = {}
def dp(i, capacity):
    if i == N:
        return 0
    if (i, capacity) in memo:
        return memo[(i, capacity)]
    ret = dp(i+1, capacity)
    w, v = WVs[i]
    if w <= capacity:
        ret2 = dp(i+1, capacity - w) + v
        ret = ret if ret > ret2 else ret2
    memo[(i, capacity)] = ret
    return ret

print(dp(0, W))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, W, WV):
    vl = {}
    vl[WV[0][0]] = list()
    vl[WV[0][0]+1] = list()
    vl[WV[0][0]+2] = list()
    vl[WV[0][0]+3] = list()
    for w, v in WV:
        vl[w].append(v)

    for v in vl.values():
        v.sort(reverse=True)
        v.insert(0, 0)


    wi, wj, wk, wl = vl.keys()
    ans = 0
    vis = 0
    for i, vi in enumerate(vl[wi]):
        if wi * i > W:
            break
        vis += vi
        vjs = 0
        for j, vj in enumerate(vl[wj]):
            if wi * i + wj * j > W:
                break
            vjs += vj
            vks = 0
            for k, vk in enumerate(vl[wk]):
                if wi*i + wj*j + wk*k> W:
                    break
                vks += vk
                vls = 0
                for l, vll in enumerate(vl[wl]):
                    if wi*i + wj*j + wk*k + wl*l> W:
                        break
                    vls += vll
                ans = max(ans, vis+vjs+vks+vls)
    return ans





def main():
    N, W = read_int_n()
    WV = [read_int_n() for _ in range(N)]
    print(slv(N, W, WV))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import accumulate 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,W = map(int,readline().split())
A1 = []
A2 = []
A3 = []
A4 = []
w1,v1 = map(int,readline().split())
A1.append(v1)

for _ in range(N-1):
    w,v = map(int,readline().split())
    if w == w1:
        A1.append(v)
    elif w == w1+1:
        A2.append(v)
    elif w == w1+2:
        A3.append(v)
    else:
        A4.append(v)

S1 = list(accumulate(sorted(A1,reverse = True)))
S2 = list(accumulate(sorted(A2,reverse = True)))
S3 = list(accumulate(sorted(A3,reverse = True)))
S4 = list(accumulate(sorted(A4,reverse = True)))

S1 = [0] + S1
S2 = [0] + S2
S3 = [0] + S3
S4 = [0] + S4

ans = 0
for a in range(len(S1)):
    for b in range(len(S2)):
        for c in range(len(S3)):
            for d in range(len(S4)):
                tmp = w1*(a+b+c+d)+b+2*c+3*d
                total = S1[a]+S2[b]+S3[c]+S4[d]
                if tmp <= W:
                    ans = max(ans,total)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    n, w = ns()
    w_list = []
    v_list = []
    for _ in range(n):
        wi, vi = ns()
        w_list.append(wi)
        v_list.append(vi)

    lim = 301
    base = w_list[0]
    dp = [[-1] * (lim + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    for wi, vi in zip(w_list, v_list):
        wi -= base
        for i in range(n - 1, -1, -1):
            base_cost = (i + 1) * base
            for j in range(lim + 1):
                if dp[i][j] != -1:
                    if j + wi + base_cost <= w:
                        dp[i + 1][j + wi] = max(dp[i + 1][j + wi], dp[i][j] + vi)

    ans = 0
    for dpi in dp:
        ans = max(ans, max(dpi))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,w = map(int,ipt().split())
    tng = [tuple(map(int,ipt().split())) for i in range(n)]
    dp = [[0]*(3*n) for i in range(n+1)]
    w1 = tng[0][0]
    ma = 0
    for ni,(wi,vi) in enumerate(tng):
        dw = wi-w1
        for i in range(ni+1,0,-1):
            for j in range(dw,3*n):
                if dp[i-1][j-dw]+vi > dp[i][j]:
                    dp[i][j] = dp[i-1][j-dw]+vi

    ans = 0
    for i in range(n+1):
        rw = w-i*w1
        if rw < 0:
            break
        ti = max(min(3*n-1,rw),0)
        if ans < dp[i][ti]:
            ans = dp[i][ti]

#    print(dp)
    print(ans)
    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
wvs = []
for i in range(N):
    w,v = map(int, input().split())
    wvs.append((w,v))
# dp : n個入っていて、合計がwのときの最大値
w0 = wvs[0][0]
dp = [[[0]*(330) for i in range(110)] for k in range(110)]
# dp[0][0][0] = 0
for i in range(N):
    w, v = wvs[i]
    dw = w-w0
    for j in range(i+1):
        for k in range(310):
            # if k - dw >= 0:
            # if dp[i][j][j] == -1:continue
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            dp[i+1][j+1][k+dw] = max(dp[i][j][k]+v, dp[i+1][j+1][k+dw])

d = dp[N]
ans = 0
for j in range(N+1):
    if W-j*w0 >= 0:
        a = max(d[j][:W-j*w0+1])
        ans = max(ans, a)
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
wvs = []
for i in range(N):
    w,v = map(int, input().split())
    wvs.append((w,v))
# dp : n個入っていて、合計がwのときの最大値
w0 = wvs[0][0]
dp = [[[-1]*(330) for i in range(110)] for k in range(110)]
dp[0][0][0] = 0
for i in range(N):
    w, v = wvs[i]
    dw = w-w0
    for j in range(i+1):
        for k in range(310):
            # if k - dw >= 0:
            # if dp[i][j][j] == -1:continue
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            dp[i+1][j+1][k+dw] = max(dp[i][j][k]+v, dp[i+1][j+1][k+dw])

d = dp[N]
ans = 0
for j in range(N+1):
    if W-j*w0 >= 0:
        a = max(d[j][:W-j*w0+1])
        ans = max(ans, a)
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
wvs = []
for i in range(N):
    w,v = map(int, input().split())
    wvs.append((w,v))
# dp : n個入っていて、合計がwのときの最大値
w0 = wvs[0][0]
dp = [[[-1]*(330) for i in range(110)] for k in range(110)]
dp[0][0][0] = 0
for i in range(N):
    w, v = wvs[i]
    dw = w-w0
    for j in range(i+1):
        for k in range(310):
            # if k - dw >= 0:
            if dp[i][j][j] == -1:continue
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            dp[i+1][j+1][k+dw] = max(dp[i][j][k]+v, dp[i+1][j+1][k+dw])

d = dp[N]
ans = 0
for j in range(N+1):
    if W-j*w0 >= 0:
        a = max(d[j][:W-j*w0+1])
        ans = max(ans, a)
print(ans)

Submission status: Accepted

Solution code:
n,w=list(map(int,input().split()))
m=0
d={0:0}
for i in range(n):
  nd={}
  a,b=list(map(int,input().split()))
  for j in d:
    if j in nd:
      nd[j]=max(nd[j],d[j])
    else:
      nd[j]=d[j]
    if j+a>w:
      continue
    if j+a in nd:
      nd[j+a]=max(nd[j+a],d[j]+b)
    else:
      nd[j+a]=d[j]+b
    m=max(m,d[j]+b)
  d=nd
print(m)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,w = list(map(int, input().split()))
wv = [None]*n
for i in range(n):
    wv[i] = tuple(map(int, input().split()))
w0 = wv[0][0]
wv = [(item[0]-w0, item[1]) for item in wv]
ans = 0
def sub(k):
    W = w - k*w0
    m = min(W, sum(item[0] for item in wv))
    dp = [[[0]*(k+1) for _ in range(m+1)] for _ in range(n+1)]
    for i in range(1,n+1):
        iw, iv = wv[i-1]
        for j in range(m+1):
            for kk in range(1,k+1):
                if j>=iw:
                    dp[i][j][kk] = max(dp[i-1][j][kk], dp[i-1][j-iw][kk-1]+iv)
                else:
                    dp[i][j][kk] = dp[i-1][j][kk]
#     print(k, dp)
    return max(dp[n][j][kk] for j in range(m+1))
for k in range(1, w//w0+1):
    if k>n:
        break
    ans = max(ans, sub(k))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,w = list(map(int, input().split()))
wv = [None]*n
for i in range(n):
    wv[i] = tuple(map(int, input().split()))
w0 = wv[0][0]
wv = [(item[0]-w0, item[1]) for item in wv]
ans = 0
def sub(k):
    W = w - k*w0
    m = min(W, sum(item[0] for item in wv))
    dp = [[[0]*(k+1) for _ in range(m+1)] for _ in range(n+1)]
    for i in range(1,n+1):
        iw, iv = wv[i-1]
        for j in range(m+1):
            for kk in range(1,k+1):
                if j>=iw:
                    dp[i][j][kk] = max(dp[i-1][j][kk], dp[i-1][j-iw][kk-1]+iv)
                else:
                    dp[i][j][kk] = dp[i-1][j][kk]
#     print(k, dp)
    return max(dp[n][j][kk] for j in range(m+1) for kk in range(k+1))
for k in range(1, w//w0+1):
    if k>n:
        break
    ans = max(ans, sub(k))
print(ans)

Submission status: Accepted

Solution code:
n,w=list(map(int,input().split()))
gds=[list(map(int,input().split())) for _ in range(n)]
w1=gds[0][0]
goods={w1+i:[0] for i in range(4)}

for cw,cv in gds:
    goods[cw].append(cv)

for i in range(4):
    goods[w1+i]=sorted(goods[w1+i],reverse=True)
ans=0

for d in range(min(w//(w1+3),len(goods[w1+3]))+1):
    wd=w-d*(w1+3)
    for c in range(min(wd//(w1+2),len(goods[w1+2]))+1):
        wc=wd-c*(w1+2)
        for b in range(min(wc//(w1+1),len(goods[w1+1]))+1):
            wb=wc-b*(w1+1)
            a=wb//w1

            ans=max(ans,sum(goods[w1][:a])+sum(goods[w1+1][:b])+sum(goods[w1+2][:c])+sum(goods[w1+3][:d]))

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, W = map(int, input().split())
d = defaultdict(int)
d[0] = 0
for i in range(n):
    w, v = map(int, input().split())
    for j, k in list(d.items()):
        if W >= j + w:
            d[j + w] = max(d[j + w], k + v)
print(max(d.values()))

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n,ww=MI()
	w1,v1=MI()
	li=[[] for _ in range(4)]
	li[0].append(v1)

	for _ in range(n-1):
		w,v=MI()
		li[w-w1].append(v)

	for i in range(4):
		li[i]=[0]+sorted(li[i],reverse=True)
	#print(li)

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

	ans=0

	for i0 in range(len(li[0])):
		for i1 in range(len(li[1])):
			for i2 in range(len(li[2])):
				for i3 in range(len(li[3])):
					#print(i0,i1,i2,i3,li[0][i0],li[1][i1],li[2][i2],li[3][i3],w1*i0+(w1+1)*i1+(w1+2)*i2+(w1+3)*i3,li[0][i0]+li[1][i1]+li[2][i2]+li[3][i3],w,ans)
					if w1*i0+(w1+1)*i1+(w1+2)*i2+(w1+3)*i3<=ww:
						ans=max(ans,li[0][i0]+li[1][i1]+li[2][i2]+li[3][i3])

	print(ans)


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,w = map(int,readline().split())
wv = list(map(int,read().split()))

inf = -1 * 10**10
dp = [[inf] * (301) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    wi,vi = wv[i*2:i*2+2]
    wi -= wv[0]
    for j in range(n,0,-1):
        for k in range(wi,301):
            dp[j][k] = max(dp[j][k], dp[j-1][k-wi] + vi)

ans = 0
for i in range(n+1):
    for j in range(301):
        if(i*wv[0] + j <= w):
            ans = max(ans,dp[i][j])

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    N, W = map(int, input().split())
    V = [[0] for _ in range(4)]
    for i in range(N):
        w, v = map(int, input().split())
        if i == 0:
            init = w
        V[w - init].append(v)

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

    res = 0
    for i in range(len(V[0]) + 1):
        a = sum(V[0][:i])
        for j in range(len(V[1]) + 1):
            b = sum(V[1][:j])
            for k in range(len(V[2]) + 1):
                c = sum(V[2][:k])
                for l in range(len(V[3]) + 1):
                    d = sum(V[3][:l])
                    total_w = init * i + (init + 1) * j + (init + 2) * k + (init + 3) * l
                    if total_w <= W:
                        res = max(res, a + b + c + d)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    N, W = map(int, input().split())
    V = [[0] for _ in range(4)]
    for i in range(N):
        w, v = map(int, input().split())
        if i == 0:
            init = w
        V[w - init].append(v)

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

    res = 0
    for i in range(len(V[0]) + 1):
        a = sum(V[0][:i])
        for j in range(len(V[1]) + 1):
            b = sum(V[1][:j])
            for k in range(len(V[2]) + 1):
                c = sum(V[2][:k])
                for l in range(len(V[3]) + 1):
                    d = sum(V[3][:l])
                    total_w = init * i + (init + 1) * j + (init + 2) * k + (init + 3) * l
                    if total_w <= W:
                        res = max(res, a + b + c + d)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N, W = na()
INF = 10 ** 12
dp = [[-INF] * (N*3+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = na()
    if i == 0:
        w1 = w
    w -= w1
    for j in range(N, 0, -1):
        for k in range(N*3, -1, -1):
            if k >= w:
                dp[j][k] = max(dp[j][k], dp[j-1][k-w] + v)

ans = 0
for i in range(1, N+1):
    wmax = W - w1 * i
    if wmax < 0:
        break
    ans = max(ans, max(dp[i][0:min(N, wmax) + 1]))

print(ans)

Submission status: Accepted

Solution code:
N, W = (int(x) for x in input().split())
dp = [[-1 for i in range(301)] for j in range(N+1)]
dp[0][0] = 0
for k in range(N):
    w, v = (int(x) for x in input().split())
    if k == 0:
        base_w = w
    for i in range(N)[::-1]:    
        for j in range(301)[::-1]:
            if dp[i][j]!=-1:
                dp[i+1][j+w-base_w] = max([dp[i][j]+v, dp[i+1][j+w-base_w]])
        
ans=0
for index,item in enumerate(dp):
    if W-index*base_w+1<=0:
        break
    ans=max(max(item[:W-index*base_w+1]),ans)

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

n, W = (int(x) for x in input().split())
WV = [tuple(int(x) for x in input().split()) for _ in range(n)]
weight = [[] for _ in range(4)]  # weight[0] ~ weight[3]
w1 = WV[0][0]
for w, v in WV:
    weight[w - w1].append(v)

for wei in weight:
    wei.sort(reverse=True)

value_acc = [[] for _ in range(4)]
for i in range(4):
    value_acc[i] = list(accumulate(weight[i]))

ans = 0
for i in range(len(weight[0]) + 1):
    for j in range(len(weight[1]) + 1):
        for k in range(len(weight[2]) + 1):
            for l in range(len(weight[3]) + 1):
                tmp = w1 * i + (w1 + 1) * j + (w1 + 2) * k + (w1 + 3) * l
                if tmp <= W:
                    value = 0
                    for x, y in zip([0, 1, 2, 3], [i, j, k, l]):
                        if y - 1 >= 0:
                            value += value_acc[x][y - 1]
                    ans = max(ans, value)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, W = (int(x) for x in input().split())
WV = [tuple(int(x) for x in input().split()) for _ in range(n)]
d = defaultdict(int)  # d[weight_sum] = max_value_sum
d[0] = 0
for i in range(n):
    w, v = WV[i]
    d_tmp = list(d.items())
    for w_sum, v_sum in d_tmp:
        if w_sum + w <= W:
            d[w_sum + w] = max(d[w_sum + w], v_sum + v)

print(max(d.values()))

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
a,b,c,d = [],[],[],[]
for i in range(N):
    w,v = map(int,input().split())
    if i == 0:
        w0 = w
    if w == w0:
        a.append(v)
    elif w == w0+1:
        b.append(v)
    elif w == w0+2:
        c.append(v)
    else:
        d.append(v)
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
d.sort(reverse=True)
A,B,C,D = len(a),len(b),len(c),len(d)
a1 = [0]*(A+1)
b1 = [0]*(B+1)
c1 = [0]*(C+1)
d1 = [0]*(D+1)
for i in range(1,A+1):
    a1[i] = a1[i-1] + a[i-1]
for i in range(1,B+1):
    b1[i] = b1[i-1] + b[i-1]
for i in range(1,C+1):
    c1[i] = c1[i-1] + c[i-1]
for i in range(1,D+1):
    d1[i] = d1[i-1] + d[i-1]
ans = 0
for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            for l in range(D+1):
                if w0*i + (w0+1)*j + (w0+2)*k + (w0+3)*l <= W:
                    ans = max(ans,a1[i]+b1[j]+c1[k]+d1[l])
                else:
                    break
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,W,*wv = map(int,read().split())

res = [[] for _ in range(n)]
w0 = wv[0]
mp = iter(wv)
for w,v in zip(mp,mp):
    res[w-w0].append(v)

from itertools import accumulate
d = [None for _ in range(4)]
for i in range(4):
    r = res[i]
    r.sort(reverse=True)
    d[i] = {(w0+i)*(j+1):wj for j,wj in enumerate(accumulate(r))}
    d[i][0] = 0
    #print(r,w0+i)
    #print(d[i])

def merge(d1,d2):
    res = {}
    for w1,v1 in d1.items():
        for w2,v2 in d2.items():
            w = w1+w2
            v = v1+v2
            if w in res: res[w] = max(res[w],v)
            else: res[w] = v
    return res    

#print(d)

d1 = merge(d[0],d[1])
d2 = merge(d[2],d[3])
dd = merge(d1,d2)

#print(d)
#print(d1)
#print(d2)
#print(dd)

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

Submission status: Accepted

Solution code:
from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

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

    for i in d.values():
        i.sort(reverse=True)

    # dict型をvalueでsort(keyでsortならkey変数削除）
    from collections import OrderedDict
    d = OrderedDict(sorted(d.items()))

    # for i in range(4-len(d)):
    # d[0].append(0)

    dlength = []
    for k, v in d.items():
        dlength.append((range(len(v)+1), k, v))

    for i in range(4-len(dlength)):
        dlength.append((range(1), 0, [0]))
    Mans = 0
    for i in dlength[0][0]:
        for j in dlength[1][0]:
            for k in dlength[2][0]:
                for l in dlength[3][0]:
                    if i*dlength[0][1]+j*dlength[1][1]+k*dlength[2][1]+l*dlength[3][1] <= W:
                        Mans = max(Mans, sum(
                            dlength[0][2][:i])+sum(dlength[1][2][:j])+sum(dlength[2][2][:k])+sum(dlength[3][2][:l]))

    print(Mans)


resolve()

Submission status: Accepted

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

for i in range(N):
    w, v = map(int, input().split())
    weights.append(w)
    values.append(v)

dp = {}
dp.setdefault(0, {})
dp[0][0] = 0

for i in range(N):
    weight_list = sorted(dp.keys(), reverse=True)
    for w in weight_list:
        dp.setdefault(w + weights[i], {})
        dp[w + weights[i]][i + 1] = max(
            max(dp[w].values()) + values[i],
            dp[w + weights[i]].get(i + 1, 0)
        )


res = 0
for w, prefix in dp.items():
    if w <= W:
        res = max(res, max(prefix.values()))

print(res)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, W = mapint()
wv = [list(mapint()) for _ in range(N)]
w0 = wv[0][0]

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

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

ans = 0
for i in range(N+1):
    if W<i*w0:
        break
    ans = max(ans, max(dp[N][i][:W-i*w0+1]))
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,W = inpl()
a = [inpl() for _ in range(n)]
gds = [[0] for _ in range(4)]
a.sort(key = lambda x:x[1], reverse = True)
a.sort(key = lambda x:x[0])
# print(a)
mi = a[0][0]
for i,(w,v) in enumerate(a):
    ind = w - mi
    gds[ind].append(v)
we = [i+mi for i in range(4)]
cnt = [0] * 4
for i in range(4):
    cnt[i] = len(gds[i])
    tmp = itertools.accumulate(gds[i])
    gds[i] = list(tmp)
# print(gds)
it = itertools.product(range(cnt[0]),range(cnt[1]),range(cnt[2]),range(cnt[3]))
res = 0
for ww in it:
    if sum(we[i]*ww[i] for i in range(4)) > W: continue
    now = sum(gds[i][ww[i]] for i in range(4))
    res = max(now, res)
print(res)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
w1 = A[0][0]
C = {0:[],1:[],2:[],3:[]}
for i in range(N):
    w,v = A[i]
    C[w-w1].append(v)
C[0] = sorted(C[0],reverse=True)
C[1] = sorted(C[1],reverse=True)
C[2] = sorted(C[2],reverse=True)
C[3] = sorted(C[3],reverse=True)
n0 = len(C[0])
n1 = len(C[1])
n2 = len(C[2])
n3 = len(C[3])
vmax = 0
for a0 in range(n0+1):
    for a1 in range(n1+1):
        for a2 in range(n2+1):
            for a3 in range(n3+1):
                if a0*w1+a1*(w1+1)+a2*(w1+2)+a3*(w1+3)<=W:
                    v = sum(C[0][:a0])+sum(C[1][:a1])+sum(C[2][:a2])+sum(C[3][:a3])
                    vmax = max(vmax,v)
print(vmax)