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:
#入力
n, W = map(int, input().split())
s = []
for i in range(n):#h:高さ
    s.append([int(m) for m in input().split()])
s.sort(key=lambda x:(x[0], x[1]))
s0 = []
s1 = []
s2 = []
s3 = []
for i in range(n):
    if i == 0:
        w0 = s[i][0]
        s0.append(s[i])
    elif s[i][0] == w0:
        s0.append(s[i])
    elif s[i][0] == w0 + 1:
        s1.append(s[i])
    elif s[i][0] == w0 + 2:
        s2.append(s[i])
    elif s[i][0] == w0 + 3:
        s3.append(s[i])
s0.sort(key=lambda x: x[1], reverse=True)
s1.sort(key=lambda x: x[1], reverse=True)
s2.sort(key=lambda x: x[1], reverse=True)
s3.sort(key=lambda x: x[1], reverse=True)
w = []
v = []
t0 = 0
t1 = 0
t2 = 0
t3 = 0
u0 = 0
u1 = 0
u2 = 0
u3 = 0
u = []
for h in range(-1, len(s0)):
    if h == -1:
        t0 = 0
        u0 = 0
    else:
        t0 += s0[h][0]
        u0 += s0[h][1]
    for i in range(-1, len(s1)):
        if i == -1:
            t1 = 0
            u1 = 0
        else:
            t1 += s1[i][0]
            u1 += s1[i][1]
        for j in range(-1, len(s2)):
            if j == -1:
                t2 = 0
                u2 = 0
            else:
                t2 += s2[j][0]
                u2 += s2[j][1]
            for k in range(-1, len(s3)):
                if k == -1:
                    t3 = 0
                    u3 = 0
                else:
                    t3 += s3[k][0]
                    u3 += s3[k][1]
                if t0 + t1 + t2 + t3 <= W:
                    u.append(u0 + u1 + u2 + u3)
print(max(u))

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
List=[[] for i in range(4)]
for i in range(N):
  w,v=map(int,input().split())
  if i==0:
    List[0].append(v)
    w0=w
  else:
    List[w-w0].append(v)
ans=0
for i in range(4):
  List[i].sort(key=lambda x:-x)
n0,n1,n2,n3=len(List[0]),len(List[1]),len(List[2]),len(List[3])
for i in range(n0+1):
  for j in range(n1+1):
    for p in range(n2+1):
      for q in range(n3+1):
        if w0*i+(w0+1)*j+(w0+2)*p+(w0+3)*q<=W:
          ans=max(ans,sum(List[0][:i])+sum(List[1][:j])+sum(List[2][:p])+sum(List[3][:q]))
print(ans)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
d={}
p=0
for i in range(n):
    a,b=map(int,input().split())
    if a in d: d[a].append(b)
    else: d[a]=[b]
    p=max(p,a)

for i in range(4):
    if p-i in d:d[p-i].sort(reverse=True)
    else: d[p-i]=[0]

l={}
for i in d:
    t=0
    l[i]=[0]
    for j in d[i]:
        t+=j
        l[i].append(t)
ans=0
for ai,i in enumerate(l[p]):
    for bj,j in enumerate(l[p-1]):
        for ck,k in enumerate(l[p-2]):
            for em,m in enumerate(l[p-3]):
                x=ai*p+bj*(p-1)+ck*(p-2)+em*(p-3)
                if x<=w:
                    ans=max(ans,i+j+k+m)
print(ans)

Submission status: Accepted

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

dp = defaultdict(int)
dp[0] = 0
for w, v in wv:
    dp_cur = list(dp.items())
    for w_cur, v_cur in dp_cur:
        if w_cur+w <= W:
            dp[w_cur+w] = max(dp[w_cur+w], v_cur+v)
print(max(dp.values()))

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import deque

N,W=list(map(int,input().split()))
arr=[deque([]) for i in range(4)]

w1,v=list(map(int,input().split()))
arr[0].append(v)

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

for i in range(4):
    arr[i]=sorted(arr[i],reverse=True)
    arr[i]=deque(accumulate(arr[i]))
    arr[i].appendleft(0)

ans=0
for i in range(len(arr[0])):
    for j in range(len(arr[1])):
        for k in range(len(arr[2])):
            for h in range(len(arr[3])):
                weight=(i+j+k+h)*w1+j+2*k+3*h
                value=arr[0][i]+arr[1][j]+arr[2][k]+arr[3][h]
                if weight>W:
                    break
                elif value>ans:
                    ans=value
print(ans)

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
data_list=[]
for j in range(N):
    w,v=map(int,input().split())
    data_list.append((w,v))
from collections import defaultdict
data = defaultdict(int)
data[0] = 0
for w, v  in data_list:
    for cw, cv in list(data.items()):
        if cw + w <= W:
            data[cw+w] = max(data[cw+w], cv + v)
print(max(data.values()))

Submission status: Accepted

Solution code:
#060-D
n,w=map(int,input().split())
v=[[] for i in range(4)]
w1,v1=map(int,input().split())
v[0].append(v1)
for i in range(1,n):
    tw,tv=map(int,input().split())
    v[tw-w1].append(tv)
for i in range(4):
    v[i].sort(reverse=True)
cum=[[0] for i in range(4)]
for i in range(4):
    for j in range(len(v[i])):
        cum[i].append(cum[i][j]+v[i][j])
s=0
for i in range(len(v[0])+1):
    for j in range(len(v[1])+1):
        for k in range(len(v[2])+1):
            for l in range(len(v[3])+1):
                if w1*(i+j+k+l)+j+2*k+3*l>w:
                    continue
                s=max(s,cum[0][i]+cum[1][j]+cum[2][k]+cum[3][l])
print(s)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
w_adjust = []
for i in range(N):
    w_adjust.append(w[i]-w[0])

a = w[0]
dp = [[[0 for i in range(N+1)] for j in range(N*3+10)] for k in range(N+1)]
#i個目までの物のうちk個選んで重さの和がjになる中での最大価値
for i in range(N):
    for j in range(3*N):
        for k in range(N):
            if j + w_adjust[i] > W - a*(k+1):
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            else:
                dp[i+1][j+w_adjust[i]][k+1] = max(dp[i+1][j+w_adjust[i]][k+1], dp[i][j][k] + v[i])
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
ans = [0]
for i in range(1, N+1):
    if W - a*i >= 0 and W - a*i < N*3 + 3:
        ans.append(dp[N][W-a*i][i])

if W - a*N > N*3:
    things = W//w[0]
    if things > N:
        ans.append(sum(v))

elif len(ans) == 1:
    things = W//w[0]
    v.sort()
    v.reverse()
    ans_1 = 0
    for i in range(things):
        ans_1 += v[i]
    ans.append(ans_1)

print(max(ans))

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
v = [[] for _ in range(4)]
w0,vv = map(int,input().split())
v[0].append(vv)
for _ in range(N-1):
    ww,vv = map(int,input().split())
    v[ww-w0].append(vv)
for i in range(4):
    v[i].sort(reverse=True)
cum =[[0] for _ in range(4)]
for i in range(4):
    for j in range(len(v[i])):
        cum[i].append(cum[i][j]+v[i][j])
ans = 0
for i in range(len(v[0])+1):
    for j in range(len(v[1])+1):
        for k in range(len(v[2])+1):
            for l in range(len(v[3])+1):
                if (i+j+k+l)*w0 + j + 2*k + 3*l > W:
                    continue
                #ここから下は制約を満たすことが保証される
                candidate = cum[0][i] + cum[1][j] + cum[2][k] + cum[3][l]
                ans = max(ans,candidate)
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
l0=[]
l1=[]
l2=[]
l3=[]
for i in range(N):
    w,v = map(int,input().split())
    if i == 0:
        w1 = w
    if w == w1:
        l0.append(v)
    elif w == w1+1:
        l1.append(v)
    elif w == w1+2:
        l2.append(v)
    elif w == w1+3:
        l3.append(v)

l0.sort()
l0.reverse()
l1.sort()
l1.reverse()
l2.sort()
l2.reverse()
l3.sort()
l3.reverse()
l0 = [0]+l0
l1 = [0]+l1
l2 = [0]+l2
l3 = [0]+l3
import numpy as np
l0 = np.cumsum(np.array(l0))
l1 = np.cumsum(np.array(l1))
l2 = np.cumsum(np.array(l2))
l3 = np.cumsum(np.array(l3))

ans = 0
for i in range(len(l0)):
    for j in range(len(l1)):
        for k in range(len(l2)):
            for l in range(len(l3)):
                if i*w1+j*(w1+1)+k*(w1+2)+l*(w1+3)<=W:
                    if ans < l0[i]+l1[j]+l2[k]+l3[l]:
                         ans = l0[i]+l1[j]+l2[k]+l3[l]

print(ans)

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
x=[[] for _ in range(4)]
w0=wv[0][0]
for w,v in wv:
    x[w-w0].append(v)
for i in range(4):
    x[i].sort()
    x[i]=x[i][::-1]
y=[[0] for i in range(4)]
for i in range(4):
    if len(x[i])>0:
        y[i].append(x[i][0])
for i in range(4):
    for j in range(1,len(x[i])):
        y[i].append(y[i][-1]+x[i][j])
res=[]
for a in range(len(x[0])+1):
    for b in range(len(x[1])+1):
        for c in range(len(x[2])+1):
            for d in range(len(x[3])+1):
                if w0*a+(w0+1)*b+(w0+2)*c+(w0+3)*d<=W:
                    res.append(y[0][a]+y[1][b]+\
                              y[2][c]+y[3][d])
print(max(res))

Submission status: Accepted

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

data = defaultdict(int)
data[0] = 0
for w, v  in data_list:
    for cw, cv in list(data.items()):
        if cw + w <= W:
            data[cw+w] = max(data[cw+w], cv + v)
print(max(data.values()))

Submission status: Accepted

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

memo = {}

def knapsack(i, j):
    key = '{}-{}'.format(i, j)
    if key in memo:
        return memo[key]
    if i == N:
        r = 0
    elif j < w[i]:
        r = knapsack(i + 1, j)
    else:
        r = max([knapsack(i + 1, j), knapsack(i + 1, j - w[i]) + v[i]])
    memo[key] = r
    return r

print(knapsack(0, W))

Submission status: Accepted

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

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

for w, v in app:
    if w == app[0][0]:
        data[0].append(v)
    elif w == app[0][0] + 1:
        data[1].append(v)
    elif w == app[0][0] + 2:
        data[2].append(v)
    elif w == app[0][0] + 3:
        data[3].append(v)

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

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

for i in range(4):
    data[i].append(0)
    data[i].sort()

ans = 0
for a in range(len(data[0])):
    for b in range(len(data[1])):
        for c in range(len(data[2])):
            for d in range(len(data[3])):
                if a * app[0][0] + b * (app[0][0]+1) + c * (app[0][0]+2) + d * (app[0][0]+3) <= W:
                    ans = max(ans, data[0][a] + data[1][b] + data[2][c] + data[3][d])

print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
V0, V1, V2, V3 = [], [], [], []
w0 = 0
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        V0.append(v)
        w0 = w
    elif w0 == w:
        V0.append(v)
    elif w0 + 1 == w:
        V1.append(v)
    elif w0 + 2 == w:
        V2.append(v)
    else:
        V3.append(v)

V0 = sorted(V0, reverse=True)
V1 = sorted(V1, reverse=True)
V2 = sorted(V2, reverse=True)
V3 = sorted(V3, reverse=True)
vl0 = len(V0)
vl1 = len(V1)
vl2 = len(V2)
vl3 = len(V3)
V0_sum = [0] * (vl0 + 1)
V1_sum = [0] * (vl1 + 1)
V2_sum = [0] * (vl2 + 1)
V3_sum = [0] * (vl3 + 1)
for i in range(1, vl0 + 1):
    V0_sum[i] = V0_sum[i - 1] + V0[i - 1]
for i in range(1, vl1 + 1):
    V1_sum[i] = V1_sum[i - 1] + V1[i - 1]
for i in range(1, vl2 + 1):
    V2_sum[i] = V2_sum[i - 1] + V2[i - 1]
for i in range(1, vl3 + 1):
    V3_sum[i] = V3_sum[i - 1] + V3[i - 1]
w1, w2, w3 = w0 + 1, w0 + 2, w0 + 3
num = 0

for v0 in range(vl0 + 1):
    for v1 in range(vl1 + 1):
        for v2 in range(vl2 + 1):
            for v3 in range(vl3 + 1):
                w = v0 * w0 + v1 * w1 + v2 * w2 + v3 * w3
                if w <= W:
                    q = V0_sum[v0] + V1_sum[v1] + V2_sum[v2] + V3_sum[v3]
                    num = max(num, q)

print(num)

Submission status: Accepted

Solution code:
# ABC 060 D
N, W = map(int,input().split())
L = [list(map(int,input().split())) for k in range(N)]

wmin = L[0][0]
M = [[],[],[],[]]
for load in L:
    M[load[0]-wmin].append(load[1])

M0 = sorted(M[0])[::-1]
M1 = sorted(M[1])[::-1]
M2 = sorted(M[2])[::-1]
M3 = sorted(M[3])[::-1]

ans = 0
for p in range(len(M0)+1):
    for q in range(len(M1)+1):
        for r in range(len(M2)+1):
            for s in range(len(M3)+1):
                weight = p*wmin + q*(wmin+1) + r*(wmin+2) + s*(wmin+3)
                if weight <= W:
                    ans = max(ans,sum(M0[:p])+sum(M1[:q])+sum(M2[:r])+sum(M3[:s]))
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w0, v0 = map(int, input().split())
W0 = [0, v0]
W1, W2, W3 = [0], [0], [0]
for i in range(N-1):
    w, v = map(int, input().split())
    if w == w0:
        W0.append(v)
    elif w == w0 + 1:
        W1.append(v)
    elif w == w0 + 2:
        W2.append(v)
    else:
        W3.append(v)
W0.sort()
W1.sort()
W2.sort()
W3.sort()
for i in range(1, len(W0)):
    W0[i] += W0[i-1]
for i in range(1, len(W1)):
    W1[i] += W1[i-1]
for i in range(1, len(W2)):
    W2[i] += W2[i-1]
for i in range(1, len(W3)):
    W3[i] += W3[i-1]

MaxValue = 0
for i in range(len(W0)):
    for j in range(len(W1)):
        for k in range(len(W2)):
            for l in range(len(W3)):
                if w0*i + (w0+1)*j + (w0+2)*k + (w0+3)*l <= W:
                    Total = (W0[-1]-W0[-1-i]) + (W1[-1]-W1[-1-j]) + (W2[-1]-W2[-1-k]) + (W3[-1]-W3[-1-l])
                    MaxValue = max(MaxValue, Total)
print(MaxValue)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

n,w = li()
wv = []
for _ in range(n):
    wv.append(tuple(li()))
    
w0 = wv[0][0]
dic = {w0+i: [] for i in range(4)}
for k,v in wv:
    dic[k].append(v)
    
for wi in range(w0,w0+4):
    dic[wi] = [0] + sorted(dic[wi], reverse=True)
    dic[wi] = list(accumulate(dic[wi]))
    
ans = 0
for idx1, w1 in enumerate(dic[w0]):
    
    for idx2, w2 in enumerate(dic[w0+1]):
        
        for idx3, w3 in enumerate(dic[w0+2]):
            
            for idx4, w4 in enumerate(dic[w0+3]):
                
                if w0*idx1 + (w0+1)*idx2 + (w0+2)*idx3 + (w0+3)*idx4 > w:
                    continue
                
                ans = max(ans, w1+w2+w3+w4)
        
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, W = map( int, input().split())
o, k = map( int, input().split())
A = [k]
B, C, D = [], [], []
for _ in range(N-1):
    w, v = map( int, input().split())
    if w == o:
        A.append(v)
    elif w == o+1:
        B.append(v)
    elif w == o+2:
        C.append(v)
    else:
        D.append(v)
A.sort(key=None, reverse = True)
B.sort(key=None, reverse = True)
C.sort(key=None, reverse = True)
D.sort(key=None, reverse = True)
A = [0] + list(accumulate(A))
B = [0] + list(accumulate(B))
C = [0] + list(accumulate(C))
D = [0] + list(accumulate(D))
# print(A)
# print(B)
# print(C)
# print(D)
ans = 0
for i in range( len(A)):
    for j in range( len(B)):
        for k in range( len(C)):
            for l in range( len(D)):
                if i*o + j*(o+1) + k*(o+2) + l*(o+3) <= W:
#                    print('{} {} {} {}'.format(i,j,k,l))
                    ans = max( ans, A[i]+B[j]+C[k]+D[l])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def dfs(i, ws, d, W):
    if i >= len(ws):
        return 0
    w = ws[i]

    ans = dfs(i + 1, ws, d, W)
    total = 0
    for j in range(len(d[w])):
        total += d[w][j]
        if (j + 1) * w <= W:
            ans = max(ans, dfs(i + 1, ws, d, W - (j + 1) * w) + total)
    return ans


def main():
    N, W = map(int, input().split())

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

    print(dfs(0, list(d.keys()), d, W))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from itertools import accumulate

n,w = li()
wi,vi = li()
w0 = wi
v_list = [[] for _ in range(4)]
v_list[0].append(vi)

for _ in range(n-1):
    wi,vi = li()
    v_list[wi-w0].append(vi)
    
for i in range(4):
    v_list[i].sort(reverse=True)
    v_list[i] = list(accumulate([0] + v_list[i]))
    
ans = 0
res = w
for w1 in range(len(v_list[0])):
    
    if w - w0*(w1) < 0:
        pass
    else:
        res1 = w - w0*(w1)
        ans1 = v_list[0][w1]
        ans = max(ans, ans1)
    

    for w2 in range(len(v_list[1])):

        if res1 - (w0+1)*(w2) < 0:
            pass
        
        else:
            res2 = res1 - (w0+1)*(w2)
            ans2 = ans1 + v_list[1][w2]
            ans = max(ans, ans2)

        
        
        for w3 in range(len(v_list[2])):
            
            if res2 - (w0+2)*(w3) < 0:
                pass
            
            else:
                res3 = res2 - (w0+2)*(w3)
                ans3 = ans2 + v_list[2][w3]
                ans = max(ans, ans3)
                
            
            for w4 in range(len(v_list[3])):

                if res3 - (w0+3)*(w4) < 0:
                    pass
                
                else:
                    res4 = res3 - (w0+3)*(w4)
                    ans4 = ans3 + v_list[3][w4]
                    ans = max(ans, ans4)

                
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from copy import copy
N,W = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]

dp = defaultdict(lambda: 0)
dp[0] = 0
for w,v in src:
    dp2 = copy(dp)
    for pw,pv in dp.items():
        if pw+w > W: continue
        defv = dp[pw+w] if pw+w in dp else 0
        dp2[pw+w] = max(defv, pv+v)
    dp = dp2
print(max(dp.values()))

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate as acc

def main():
    N, W = map(int, input().split())
    V = [[] for _ in '1234']

    w, v = map(int, input().split())
    w0 = w
    V[0].append(v)
    for e in sys.stdin:
        w, v = map(int, e.split())
        V[w - w0].append(v)

    for i in range(4):
        V[i] = [0] + list(acc(sorted(V[i], reverse=True)))

    ans = 0
    a, b, c, d = map(len, V)
    for i in range(a):
        wi = w0 * i
        if wi > W:
            break
        vi = V[0][i]
        for j in range(b):
            wj = wi + (w0 + 1) * j
            if wj > W:
                break
            vj = vi + V[1][j]
            for k in range(c):
                wk = wj + (w0 + 2) * k
                if wk > W:
                    break
                vk = vj + V[2][k]

                l = min((W - wk) // (w0 + 3), d - 1)
                v = vk + V[3][l]
                ans = max(ans, v)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
V = [[] for i in range(4)]
w0, v0 = map(int, input().split())
V[0].append(v0)
for i in range(N - 1):
  w, v = map(int, input().split())
  V[w - w0].append(v)
V = [[0] + sorted(V[i], reverse=True) for i in range(4)]
value = 0
val = [0] * 4
for i in range(min(W // w0 + 1, len(V[0]))):
  val[0] += V[0][i]
  for j in range(min((W - w0 * i) // (w0 + 1) + 1, len(V[1]))):
    val[0] += V[1][j]
    val[1] += V[1][j]
    for k in range(min((W - w0 * (i + j) - j) // (w0 + 2) + 1, len(V[2]))):
      val[0] += V[2][k]
      val[2] += V[2][k]
      for l in range(min((W - w0 * (i + j + k) - j - k * 2) // (w0 + 3) + 1, len(V[3]))):
        val[0] += V[3][l]
        val[3] += V[3][l]
      value = max(value, val[0])
      val[0] -= val[3]
      val[3] = 0
    val[0] -= val[2]
    val[2] = 0
  val[0] -= val[1]
  val[1] = 0
print(value)

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
w1,v1 = map(int,input().split())
if n == 1:
    if w1 <= w:
        print(v1)
    else:
        print(0)
else:
    a = [v1] 
    b = []
    c = []
    d = []
    for i in range(n-1):
        p,q = map(int,input().split())
        if p == w1:
            a.append(q)
        elif p == w1 + 1:
            b.append(q)
        elif p == w1 + 2:
            c.append(q)
        else:
            d.append(q)
    a.sort()
    b.sort()
    c.sort()
    d.sort()
    a = a[::-1]
    b = b[::-1]
    c = c[::-1]
    d = d[::-1]
    #print(a,b,c,d)
    jkl = 0
    ass = 0
    for i in range(len(a)+1):
        for j in range(len(b)+1):
            for h in range(len(c)+1):
                for g in range(len(d)+1):
                    if w1*(i+j+h+g)+j+2*h+3*g <= w:
                        ans = sum(a[:i:]) + sum(b[:j:]) + sum(c[:h:]) + sum(d[:g:])
                        ass = max(ass,ans)
    print(ass)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from itertools import accumulate as ac
from itertools import product as pr

N,W=map(int,input().split())
d=dd(list)
for _ in range(N):
  w,v=map(int,input().split())
  d[w].extend([v])
d=dict(d)
for i in d.keys():
  d[i].sort(reverse=True)
  d[i]=[0]+list(ac(d[i]))

l=[]
key=list(d.keys())
for val in pr(*map(enumerate,d.values())):
  weight=sum(map(lambda x,y:x*y[0],key,val))
  value=sum(map(lambda x:x[1],val))
  if weight<=W:
    l.extend([value])

print(max(l))

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
x = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    if i == 0:
      ti = x1
      zero = 0
      iti = 0
      ni = 0
      san = 0
    if x1 == ti:
      zero += 1
    elif x1 == ti+1:
      iti += 1
    elif x1 == ti+2:
      ni += 1
    else:
      san +=1
    x.append([x1,y1])
x.sort()
zer = x[:zero]
one = x[zero:iti+zero]
two = x[iti+zero:iti+ni+zero]
three = x[iti+ni+zero:zero+iti+ni+san]
zer.append([0,0])
one.append([0,0])
two.append([0,0])
three.append([0,0])
zer = sorted(zer,key = lambda x: -x[1])
one = sorted(one,key = lambda x: -x[1])
two = sorted(two,key = lambda x: -x[1])
three = sorted(three,key = lambda x: -x[1])
ans = 0
zer0 = [0]* len(zer)+ [0]
one0 = [0]* len(one)+ [0]
two0 = [0]* len(two)+ [0]
three0 = [0]* len(three)+ [0]
zerk = [0]* len(zer)+ [0]
onek = [0]* len(one)+ [0]
twok = [0]* len(two)+ [0]
threek = [0]* len(three)+ [0]
for i in range(1,len(zer)+1):
  zer0[i] = zer0[i-1] + zer[i-1][0]
  zerk[i] = zerk[i-1] + zer[i-1][1]
for i in range(1,len(one)+1):
  one0[i] = one0[i-1] + one[i-1][0]
  onek[i] = onek[i-1] + one[i-1][1]
for i in range(1,len(two)+1):
  two0[i] = two0[i-1] + two[i-1][0]
  twok[i] = twok[i-1] + two[i-1][1]
for i in range(1,len(three)+1):
  three0[i] = three0[i-1] + three[i-1][0]
  threek[i] = threek[i-1] + three[i-1][1]
for i in range(len(zer)):
  for j in range(len(one)):
    for k in range(len(two)):
      for l in range(len(three)):
        omo = zer0[i] + one0[j] + two0[k] + three0[l]
        kati  = zerk[i] + onek[j] + twok[k] + threek[l]
        if omo <= w:
          ans = max(ans,kati)
print(ans)

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
t=[[] for i in range(4)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
    t[w[i]-w[0]].append(v[i])
for i in range(4):
    t[i].sort(reverse=True)
ans=0
s=[[0 for j in range(len(t[i])+1)] for i in range(4)]
for i in range(4):
    for j in range(1,len(t[i])+1):
        s[i][j]=s[i][j-1]+t[i][j-1]
for a0 in range(len(s[0])):
    for a1 in range(len(s[1])):
        for a2 in range(len(s[2])):
            for a3 in range(len(s[3])):
                tmp=s[0][a0]+s[1][a1]+s[2][a2]+s[3][a3]
                wt=a0*w[0]+a1*(w[0]+1)+a2*(w[0]+2)+a3*(w[0]+3)
                if wt>W:
                    continue
                if ans<tmp:
                    ans=tmp
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int,raw_input().split())

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

w,v = map(int,raw_input().split())
arr[0].append(v)
arr[1].append(0)
arr[2].append(0)
arr[3].append(0)

for i in range(1,n):
	weight , value = map(int,raw_input().split())

	arr[weight - w].append(value)

ans = 0

for i in range(4):
	arr[i].sort()
	arr[i].reverse()


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

print ans

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().split()))


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, W, WV):
    items = defaultdict(list)
    for w, v in WV:
        items[w].append(v)

    for w in items:
        items[w].sort(reverse=True)

    for i in range(4-len(items)):
        items[-i] = []
    ws = list(items.keys())

    @lru_cache(maxsize=None)
    def f(rw, i, j, k, l):
        ret = 0
        if ws[0] <= rw and i < len(items[ws[0]]):
            ret = max(ret, f(rw - ws[0], i+1, j, k, l) + items[ws[0]][i])
        if ws[1] <= rw and j < len(items[ws[1]]):
            ret = max(ret, f(rw - ws[1], i, j+1, k, l) + items[ws[1]][j])
        if ws[2] <= rw and k < len(items[ws[2]]):
            ret = max(ret, f(rw - ws[2], i, j, k+1, l) + items[ws[2]][k])
        if ws[3] <= rw and l < len(items[ws[3]]):
            ret = max(ret, f(rw - ws[3], i, j, k, l+1) + items[ws[3]][l])

        return ret

    return f(W, 0, 0, 0, 0)


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:
from collections import defaultdict
n, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]

dp = defaultdict(int)
dp[0] = 0
for w, v in wv:
    dp_cur = list(dp.items())
    for w_cur, v_cur in dp_cur:
        if w_cur+w <= W:
            dp[w_cur+w] = max(dp[w_cur+w], v_cur+v)

# print(dp)
print(max(dp.values()))

Submission status: Accepted

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

w0 = wv[0][0]
wv_dict = {w0:[], w0+1:[], w0+2:[], w0+3:[]}
for w, v in wv:
    wv_dict[w].append(v)
for w, vs in wv_dict.items():
    vs = sorted(vs)[::-1]
    wv_dict[w] = [0]
    for v in vs:
        wv_dict[w].append(v + wv_dict[w][-1])
# print(wv_dict)

ans = 0
for i in range(len(wv_dict[w0])):
    for j in range(len(wv_dict[w0+1])):
        for k in range(len(wv_dict[w0+2])):
            for l in range(len(wv_dict[w0+3])):
                w_sum = i*w0 + j*(w0+1) + k*(w0+2) + l*(w0+3)
                if w_sum > W: continue

                ans = max(ans, wv_dict[w0][i]+wv_dict[w0+1][j]+wv_dict[w0+2][k]+wv_dict[w0+3][l])
print(ans)

Submission status: Accepted

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

w_std,v = map(int,input().split())
v_list[0].append(v)
for i in range(N-1):
    wi,vi = map(int,input().split())
    v_list[wi-w_std].append(vi)
for i in range(4):
    v_list[i].sort(reverse=True)
    v_list[i].insert(0,0)

for i in range(4):
    if (len(v_list[i]) > 1):
        for j in range(1,len(v_list[i])):
            v_list[i][j] += v_list[i][j-1]

max_v = 0
for i in range(len(v_list[0])):
    for j in range(len(v_list[1])):
        for k in range(len((v_list[2]))):
            for l in range(len(v_list[3])):
                if (W >= i*w_std+j*(w_std+1)+k*(w_std+2)+l*(w_std+3)):
                    max_v = max(max_v,v_list[0][i]+v_list[1][j]+v_list[2][k]+v_list[3][l])
print(max_v)