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:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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


w,v = map(int,(input().split()))
min_w = w
wv[0].append(v)

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

wv[0].sort(reverse=True)
wv[1].sort(reverse=True)
wv[2].sort(reverse=True)
wv[3].sort(reverse=True)
L1 = len(wv[0])
L2 = len(wv[1])
L3 = len(wv[2])
L4 = len(wv[3])

SUM = 0
sum_wv1 = [0]
for i in range(L1):
	SUM += wv[0][i]
	sum_wv1.append(SUM)

SUM = 0
sum_wv2 = [0]
for i in range(L2):
	SUM += wv[1][i]
	sum_wv2.append(SUM)

SUM = 0
sum_wv3 = [0]
for i in range(L3):
	SUM += wv[2][i]
	sum_wv3.append(SUM)

SUM = 0
sum_wv4 = [0]
for i in range(L4):
	SUM += wv[3][i]
	sum_wv4.append(SUM)

ans = 0

for n1 in range(L1+1):
	for n2 in range(L2+1):
		for n3 in range(L3+1):
			for n4 in range(L4+1):
				weight = min_w*(n1+n2+n3+n4) + n2 + 2*n3 + 3*n4
				if weight <= W:
					ans = max(ans,sum_wv1[n1]+sum_wv2[n2]+sum_wv3[n3]+sum_wv4[n4])

print(ans)

Submission status: Accepted

Solution code:
def d_simple_knapsack(N, W, Baggage):
    from collections import defaultdict
    # dp[w]:ナップサックに重さがwになるように荷物を入れたときの価値の最大値
    dp = defaultdict(int)
    dp[0] = 0  # 重さ0で達成できる価値は0とする
    for w, v in Baggage:
        # dpの各要素(現時点におけるナップサック内の荷物の重さ)に対して、
        # 注目した荷物を入れても重さがWを超えなければ、
        # ナップサックに荷物を入れて価値の最大値を更新する
        latest_dp = list(dp.items())
        for kw, kv in latest_dp:
            if kw + w <= W:
                dp[kw + w] = max(dp[kw + w], kv + v)
    ans = max(dp.values())
    return ans

N, W = [int(i) for i in input().split()]
Baggage = [[int(i) for i in input().split()] for j in range(N)]
print(d_simple_knapsack(N, W, Baggage))

Submission status: Accepted

Solution code:
from collections import defaultdict


N,W = map(int, input().split())
WV = []
for i in range(N):
    WV.append(list(map(int, input().split())))
    
dp = defaultdict(int)

dp[0] = 0

for w,v in WV:
    for new_w, new_v in list(dp.items()):
        if w + new_w <= W:
            dp[w + new_w] = max(dp[w + new_w], v + new_v)
            
print(max(dp.values()))

Submission status: Accepted

Solution code:
def d_simple_knapsack(N, W, Baggage):
    from collections import defaultdict
    # dp[w]:ナップサックに重さがwになるように荷物を入れたときの価値の最大値
    dp = defaultdict(int)
    dp[0] = 0  # 重さ0で達成できる価値は0とする
    for w, v in Baggage:
        # dpの各要素(現時点におけるナップサック内の荷物の重さ)に対して、
        # 注目した荷物を入れても重さがWを超えなければ、
        # ナップサックに荷物を入れて価値の最大値を更新する
        tmp = defaultdict(int)  # 価値の最大値を更新できた荷物の重さの情報
        for kw, kv in dp.items():
            if kw + w <= W:
                if kw + w in dp:
                    tmp[kw + w] = max(dp[kw + w], kv + v)
                else:
                    tmp[kw + w] = kv + v
        for key, value in tmp.items():
            dp[key] = value
    ans = max(dp.values())
    return ans

N, W = [int(i) for i in input().split()]
Baggage = [[int(i) for i in input().split()] for j in range(N)]
print(d_simple_knapsack(N, W, Baggage))

Submission status: Accepted

Solution code:

from collections import defaultdict

N,W = map(int, input().split())
WV = []
for i in range(N):
    WV.append(list(map(int, input().split())))

dp = defaultdict(int)

dp[0] = 0

for w,v in WV:
    for nw, nv in list(dp.items()):
        if nw+w <= W:
            dp[nw+w] = max(dp[nw+w], nv+v)
            
print(max(dp.values()))

Submission status: Accepted

Solution code:
n,m=input().split()
N = int(n)
M = int(m)
w_list = []
v_list = []
w1_values = []
w2_values = []
w3_values = []
w4_values = []
sum_w1_values = []
sum_w2_values = []
sum_w3_values = []
sum_w4_values = []
sum_v1 = 0
sum_v2 = 0
sum_v3 = 0
sum_v4 = 0

for i in range(N):
	w,v = input().split()
	w = int(w)
	v = int(v)
	w_list.append(w)
	v_list.append(v)

w1 = w_list[0]
for j in range(N):
	if(w_list[j] == w1):
		w1_values.append(v_list[j])

	elif(w_list[j] == w1+1):
		w2_values.append(v_list[j])

	elif(w_list[j] == w1+2):
		w3_values.append(v_list[j])

	elif(w_list[j] == w1+3):
		w4_values.append(v_list[j])

w1_values.sort()
w1_values.reverse()
w2_values.sort()
w2_values.reverse()
w3_values.sort()
w3_values.reverse()
w4_values.sort()
w4_values.reverse()

for p in range(len(w1_values)):
	sum_v1 += w1_values[p]
	sum_w1_values.append(sum_v1)

for q in range(len(w2_values)):
	sum_v2 += w2_values[q]
	sum_w2_values.append(sum_v2)

for r in range(len(w3_values)):
	sum_v3 += w3_values[r]
	sum_w3_values.append(sum_v3)

for s in range(len(w4_values)):
	sum_v4 += w4_values[s]
	sum_w4_values.append(sum_v4)


sum_w1_values.insert(0,0)
sum_w2_values.insert(0,0)
sum_w3_values.insert(0,0)
sum_w4_values.insert(0,0)

max_value = 0
count = 0
for w in range(len(sum_w4_values)):
	for x in range(len(sum_w3_values)):
		for y in range(len(sum_w2_values)):
			for z in range(len(sum_w1_values)):
				count = w+x+y+z
				weight = (w1)*z + (w1+1)*y +(w1+2)*x + (w1+3)*w
				if(count<=N and weight<=M and max_value<(sum_w1_values[z] + sum_w2_values[y] + sum_w3_values[x] + sum_w4_values[w])):
					max_value = sum_w1_values[z] + sum_w2_values[y] + sum_w3_values[x] + sum_w4_values[w]


print(max_value)

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
weighta = []
weightb = []
weightc = []
weightd = []
for i in range(n):
	wtemp,vtemp = map(int,input().split())
	if i == 0:
		weighta.append(vtemp)
		first = wtemp
	elif wtemp == first:
		weighta.append(vtemp)
	elif wtemp == first+1:
		weightb.append(vtemp)
	elif wtemp == first+2:
		weightc.append(vtemp)
	elif wtemp == first+3:
		weightd.append(vtemp)

weighta.sort()
weighta.reverse()
weightb.sort()
weightb.reverse()
weightc.sort()
weightc.reverse()
weightd.sort()
weightd.reverse()

cuma = [0]
for i in range(len(weighta)):
	cuma.append(weighta[i]+cuma[i])
cumb = [0]
for i in range(len(weightb)):
	cumb.append(weightb[i]+cumb[i])
cumc = [0]
for i in range(len(weightc)):
	cumc.append(weightc[i]+cumc[i])
cumd = [0]
for i in range(len(weightd)):
	cumd.append(weightd[i]+cumd[i])

wa = first
wb = first+1
wc = first+2
wd = first+3

max = 0
for a in range(len(weighta)+1):
	for b in range(len(weightb)+1):
		for c in range(len(weightc)+1):
			for d in range(len(weightd)+1):
				if wa*a + wb*b + wc*c + wd*d <= w:
					t = cuma[a]-cuma[0] + cumb[b]-cumb[0] + cumc[c]-cumc[0] + cumd[d]-cumd[0]
					if t > max:
						max = t
print(max)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, W = map(int, input().split())
dd = defaultdict(int)
dd[0] = 0
for i in range(N):
    w, v = map(int, input().split())
    ddOld = dd.copy()
    ddOld2 = dd.copy()
    for dk, dv in ddOld.items():
        dd[dk+w] = max(ddOld2[dk+w], dv+v)
ans = 0
for dk, dv in dd.items():
    if dk <= W:
        ans = max(ans, dv)
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(tuple(map(int, input().split())))
w0, v0 = wv[0]
L = (N+1) * 3
dp = [[-1] * L for _ in range(N + 1)]
dp[0][0] = 0
for w,v in wv :
    for k in range(N-1, -1,  -1):
        for t in range(len(dp[k])):
            if dp[k][t] >= 0:
                dp[k+1][t+w-w0] = max(dp[k][t] + v, dp[k+1][t + w - w0])
ans = 0
for k in range(N+1):
    if w0 * k  > W : continue
    ans = max(max(dp[k][:max(min(L, W - w0 * k + 1), 0)]), ans)
print(ans)

Submission status: Accepted

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

w, v = map(int,input().split())
w0 = w
V[0].append(v)

for _ in range(N-1):
    w, v = map(int,input().split())
    V[w-w0].append(v)
for i in range(4):
    V[i].sort(reverse=True)
    for j in range(1,len(V[i])):
        V[i][j] = V[i][j-1]+V[i][j]
    V[i].insert(0,0)
    V[i].append(0)

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

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

Submission status: Accepted

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

w0,v0 = map(int,input().split())
W0,W1,W2,W3 = [],[],[],[]
W0.append(v0)
for i in range(1,N):
    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(reverse=True)
W1.sort(reverse=True)
W2.sort(reverse=True)
W3.sort(reverse=True)
V0 = [0]+list(accumulate(W0))
V1 = [0]+list(accumulate(W1))
V2 = [0]+list(accumulate(W2))
V3 = [0]+list(accumulate(W3))

Ans = 0
for i0 in range(len(V0)):
    for i1 in range(len(V1)):
        for i2 in range(len(V2)):
            for i3 in range(len(V3)):
                if w0*i0 + (w0+1)*i1 + (w0+2)*i2 + (w0+3)*i3 <= W:
                    Ans = max(Ans,V0[i0]+V1[i1]+V2[i2]+V3[i3])

print(Ans)

Submission status: Accepted

Solution code:
n,w = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(n)]
x,y,z,num,ans = sorted(x)[::-1],[0,0,0,0],[[0] for i in range(4)],x[0][0],0
for i,j in x:
	y[i-num] += 1
	z[i-num].append(z[i-num][-1]+j)
for i1 in range(y[0]+1):
	for i2 in range(y[1]+1):
		for i3 in range(y[2]+1):
			for i4 in range(y[3]+1):
				if (i1+i2+i3+i4)*num+i2+2*i3+3*i4>w: break
				else: ans = max(ans,z[0][i1]+z[1][i2]+z[2][i3]+z[3][i4])
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

N,W=map(int,input().split())

W0=[]
W1=[]
W2=[]
W3=[]

w,v=map(int,input().split())
W0.append(v)

for i in range(1,N):
  a,b=map(int,input().split())
  if a-w==0:
    W0.append(b)
  elif a-w==1:
    W1.append(b)
  elif a-w==2:
    W2.append(b)
  else:
    W3.append(b)

W0.sort(reverse=True)
W1.sort(reverse=True)
W2.sort(reverse=True)
W3.sort(reverse=True)
W0=list(accumulate(W0))
W0=[0]+W0
W1=list(accumulate(W1))
W1=[0]+W1
W2=list(accumulate(W2))
W2=[0]+W2
W3=list(accumulate(W3))
W3=[0]+W3

ans=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 w*i + (w+1)*j + (w+2)*k + (w+3)*l <= W:
          ans=max(ans,W0[i]+W1[j]+W2[k]+W3[l])
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
w_in, v = map(int,input().split())
table = [[] for i in range(4)]
table[0].append(v)
for i in range(N-1):
    w, v = map(int,input().split())
    table[w-w_in].append(v)
for i in range(4):
    table[i].sort(reverse=True)
    for j in range(len(table[i])-1):
            table[i][j+1] += table[i][j]
    table[i].insert(0,0)
ans = 0
for i in range(len(table[0])):
    for j in range(len(table[1])):
        for k in range(len(table[2])):
            for l in range(len(table[3])):
                if w_in*i+(w_in+1)*j+(w_in+2)*k+(w_in+3)*l <= W:
                    ans = max(ans, table[0][i]+table[1][j]+table[2][k]+table[3][l])
print(ans)

Submission status: Accepted

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

for wi, vi in wv:
    plus = wi - standard
    v[plus].append(vi)

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

ans = 0
for a in range(len(v[0])):
    for b in range(len(v[1])):
        for c in range(len(v[2])):
            for d in range(len(v[3])):
                if standard*a + (standard+1)*b + (standard+2)*c + (standard+3)*d > W:
                    continue
                else:
                    ans = max(ans, v[0][a]+v[1][b]+v[2][c]+v[3][d])
print(ans)

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,w]=i2()
a=[]
dp=[[-1 for j in range(100400)]for i in range(n+1)]
dp[0][0]=0
for i in range(n):
 a.append(i2())
b=a[0][0]
c=0
for i in range(1,n+1):
 for j in range(100400):
   dp[i][j]=max(dp[i][j],dp[i-1][j])
   k1=j//1000
   k2=j%1000
   if k1*b+k2<=w and j-1000-a[i-1][0]+b>=0 and dp[i-1][j-1000-a[i-1][0]+b]>=0:
     if dp[i][j]<dp[i-1][j-1000-a[i-1][0]+b]+a[i-1][1]:
        dp[i][j]=dp[i-1][j-1000-a[i-1][0]+b]+a[i-1][1]

   if c<dp[i][j]:
     c=dp[i][j]
     
print(c)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
https://abc060.contest.atcoder.jp/tasks/arc073_b

"""
import sys
from sys import stdin
input = stdin.readline


def normal_dp(items, N, W):
    dp = [[0] * (W+1) for _ in range(N+1)]

    for y in range(1, N+1):
        w = items[y-1][0]
        v = items[y-1][1]
        for x in range(1, W+1):
            if x >= w:
                dp[y][x] = max(dp[y-1][x-w] + v, dp[y-1][x])
            else:
                dp[y][x] = dp[y-1][x]
    return dp[-1][-1]


def solve(items, N, W):
    items.sort(reverse=True)

    c_items = [[] for _ in range(4)] #  同じ重さのアイテムをまとめたもの、vで降順ソート済。[0]が一番軽いアイテムで[3]が+3だけ重い。
    min_w = items[-1][0]
    for w, v in items:
        c_items[w - min_w].append(v)
    for l in c_items:
        l.append(0)

    # ある重さのアイテムをn個選択したときのベストなvの値を計算しておく
    accumulated_v = [[0] for _ in range(4)]
    for i in range(4):
        for j, v in enumerate(c_items[i], start=1):
            accumulated_v[i].append(accumulated_v[i][-1] + v)

    total_values = []
    for iw0 in range(len(c_items[0])):
        for iw1 in range(len(c_items[1])):
            for iw2 in range(len(c_items[2])):
                for iw3 in range(len(c_items[3])):
                    total_w = (iw0 * min_w) + (iw1 * (min_w+1)) + (iw2 * (min_w+2)) + (iw3 * (min_w+3))
                    if total_w <= W:
                        total_v = accumulated_v[0][iw0] + accumulated_v[1][iw1] + accumulated_v[2][iw2] + accumulated_v[3][iw3]
                        total_values.append(total_v)
    return max(total_values)



def main(args):
    items = []
    N, W = map(int, input().split())
    for _ in range(N):
        w, v = map(int, input().split())
        items.append([w, v])
    items.sort()
    ans = solve(items, N, W)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
def d_SimpleKnapsack(N, W, T):
    from collections import defaultdict
    # dp[i]は、ナップサックに重さの和がiになるように物を入れたときの
    # 価値の最大値が格納される
    dp = defaultdict(int)
    dp[0] = 0  # 重さ0で達成できる価値は0とする
    for w, v in T:
        for nw, nv in list(dp.items()):
            # 今のdpの要素それぞれに対して、
            # 注目している物を入れて重さがWを超えなければ、
            # 物を入れて価値の最大値を更新する
            if nw + w <= W:
                dp[nw + w] = max(dp[nw + w], nv + v)
    return max(dp.values())

N,W = [int(i) for i in input().split()]
T = [[int(i) for i in input().split()] for j in range(N)]
print(d_SimpleKnapsack(N, W, T))

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())
minW = min(w)
for i in range(N):
    w[i] -= minW
MAX_W = 3 * 100
MAX_V = int(1e9)
INF = MAX_V + 2
dp = [[-INF] * (MAX_W + 10) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(MAX_W, -1, -1):
        for k in range(N-1, -1, -1):
            dp[k+1][j+w[i]] = max((dp[k+1][j+w[i]], dp[k][j] + v[i]))

ans = 0
for i in range(N+1):
    for j in range(MAX_W + 1):
        if i * minW + j <= W:
            # print('i * minW: %d, j: %d, dp: %d' % (i*minW, j, dp[i][j]))
            ans = max((ans, dp[i][j]))

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,W=map(int,raw_input().split())
wv=[]

for i in range(N):
	w,v=map(int,raw_input().split())
	wv.append((w,v))


dp=defaultdict(lambda: 0)	# Weight:Value
dp[0]=0

for w1,v1 in wv:
	d=dp.copy()
	for w,v in dp.items():
		dp[w+w1]=max( dp[w+w1], d[w]+v1 )


l1=filter(lambda x:x[0]<=W , dp.items())
print sorted(l1, key=lambda x: x[1],reverse=True)[0][1]

Submission status: Accepted

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

a=defaultdict(lambda:[])
for i in range(N):
	w,v=map(int,raw_input().split())
	a[w]=a[w]+[v]

for i,j in a.items():
	a[i]=sorted(j,reverse=True)



lst=[]
for i,j in a.items():
	lst.append( (i,len(j)) )

max_val=0
if len(lst)==1:
	w1=lst[0][0]
	c1=lst[0][1]
	for i in range(c1+1):
		if i*w1<=W:
			max_val=max(max_val, sum(a[w1][:i]))

elif len(lst)==2:
	w1=lst[0][0]; w2=lst[1][0]
	c1=lst[0][1]; c2=lst[1][1]
	for i in range(c1+1):
		for j in range(c2+1):
				if i*w1+j*w2<=W:
					max_val=max(max_val, sum(a[w1][:i])+sum(a[w2][:j]))

elif len(lst)==3:
	w1=lst[0][0]; w2=lst[1][0]; w3=lst[2][0]
	c1=lst[0][1]; c2=lst[1][1]; c3=lst[2][1]
	for i in range(c1+1):
		for j in range(c2+1):
			for k in range(c3+1):
				if i*w1+j*w2+k*w3<=W:
					max_val=max(max_val, sum(a[w1][:i])+sum(a[w2][:j])+sum(a[w3][:k]))

elif len(lst)==4:
	w1=lst[0][0]; w2=lst[1][0]; w3=lst[2][0]; w4=lst[3][0]
	c1=lst[0][1]; c2=lst[1][1]; c3=lst[2][1]; c4=lst[3][1]
	for i in range(c1+1):
		for j in range(c2+1):
			for k in range(c3+1):
				for m in range(c4+1):
					if i*w1+j*w2+k*w3+m*w4<=W:
						max_val=max(max_val, sum(a[w1][:i])+sum(a[w2][:j])+sum(a[w3][:k])+sum(a[w4][:m]))

print max_val

Submission status: Accepted

Solution code:
import itertools

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

minW = items[0][0]
arrVs = [[] for i in range(4)]
for w, v in items:
    arrVs[w - minW].append(v)

acc = [[] for i in range(4)]
for i, arrV in enumerate(arrVs):
    arrV.sort(reverse=True)
    acc[i] = [0] + list(itertools.accumulate(arrV))

num = [range(len(acc[i])) for i in range(4)]

ans = 0
for n in itertools.product(num[0], num[1], num[2], num[3]):
    w = sum([n[i] * (minW + i) for i in range(4)])
    v = sum([acc[i][n[i]] for i in range(4)])
    if w <= W:
        ans = max(ans, v)

print(ans)

Submission status: Accepted

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

memo = [{} for i in range(N + 1)]

memo[0] = {0: 0}
for i, (wi, vi) in enumerate(items):
    for w, v in memo[i].items():

        if w + wi <= W:
            memo[i + 1][w + wi] = max(memo[i + 1].get(w + wi, 0), v + vi)

        memo[i + 1][w] = max(memo[i + 1].get(w, 0), v)

print(max(memo[N].values()))

Submission status: Accepted

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

w0 = items[0][0]
sizeX = min(W, sum([items[i][0] for i in range(N)])) // w0 + 1
sizeY = min(w0, 3 * (N - 1) + 1)
memo = [[[-1 for y in range(sizeY)] for x in range(sizeX)] for i in range(N + 1)]

memo[0][0][0] = 0
for i, (wi, vi) in enumerate(items):
    for x in range(sizeX):
        for y in range(sizeY):
            if memo[i][x][y] == -1: continue

            wn = w0 * x + y + wi
            if wn <= W:
                memo[i + 1][wn // w0][wn % w0] = memo[i][x][y] + vi

            memo[i + 1][x][y] = max(memo[i + 1][x][y], memo[i][x][y])

print(max(map(max, [memo[N][x] for x in range(sizeX)])))

Submission status: Accepted

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

values = [[] for n in range(4)]
w, v = [int(n) for n in input().split()]
w_0 = w
values[0].append(v)

sum_values = [[0] for n in range(4)]


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

for i in range(4):
  values[i].sort(reverse=True)
  s = 0
  for j in range(len(values[i])):
    s += values[i][j]
    sum_values[i].append(s)

res = 0
for i in range(len(values[0])+1):
  for j in range(len(values[1])+1):
    for k in range(len(values[2])+1):
      for l in range(len(values[3])+1):
        if (i*w_0 + j*(w_0+1) + k*(w_0+2) + l*(w_0+3))<=W:
          res = max(res, sum_values[0][i]+sum_values[1][j]+sum_values[2][k]+sum_values[3][l])


print(res)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
dic=[[],[],[],[]]
a,b=map(int,input().split())
dic[0].append(b)
p=a
v=[1,0,0,0]
for i in range(n-1):
    a,b=map(int,input().split())
    dic[a-p].append(b)
    v[a-p]+=1
for i in range(4):
    dic[i]=sorted(dic[i],reverse=True)
    for j in range(1,v[i]):
        dic[i][j]=dic[i][j]+dic[i][j-1]
    dic[i].insert(0,0)
max_v=0
for i in range(v[0]+1):
    for j in range(v[1]+1):
        for k in range(v[2]+1):
            for l in range(v[3]+1):
                if i*p+j*(p+1)+k*(p+2)+l*(p+3)<=w:
                    max_v=max(max_v,dic[0][i]+dic[1][j]+dic[2][k]+dic[3][l])
print(max_v)

Submission status: Accepted

Solution code:
import sys
N,W = map(int, raw_input().split())
src = []
wmax = vmax = 0
for i in range(N):
  w,v = map(int, raw_input().split())
  src.append((w,v))
  wmax += w
  vmax += v
w1 = src[0][0]

if w1 > W:
  print(0)
  sys.exit()
if wmax <= W:
  print(vmax)
  sys.exit()

wend = 3*N+1
dp = [[0 for w in range(wend)] for n in range(N+1)]
for i in range(N):
  wi,vi = src[i]
  wi -= w1 # 0 <= wi <= 3
  maxn = min(N,i+1)
  for n in reversed(range(1,maxn+1)):
    for w in range(wi,wend):
      dp[n][w] = max(dp[n][w], dp[n-1][w-wi] + vi)

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

print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
    
memo = {}

def nap(i, j):
    if i == N:
        return 0
    
    if (i, j) in memo:
        return memo[i, j]
    elif j < w[i]:
        temp = nap(i+1, j)
    else:
        temp = max(nap(i+1, j), nap(i+1, j-w[i]) + v[i])
    
    memo[i,j] = temp
    
    return memo[i,j]

print(nap(0, W))

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import product

N, W = map(int, input().split())
items = {}
weight = []

for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    
    if items.get(w, None) is None:
        items[w] = []
    items[w].append(v)
    items[w] = sorted(items[w], reverse = True)

cnt = Counter(weight)

w_num = [] #各重さの個数。組み合わせのために使う。[range(0,2), range(0,3), range(0,2)]のような出力
w_set = [] # 重さは w0 <= wi <= w0+3の４通りしかない

for w in range(weight[0], weight[0] + 4):
    if cnt[w] == 0:
        continue
    
    w_num.append(range(cnt[w] + 1))
    w_set.append(w)

ans = 0

for i in product(*w_num):
    w = sum(map(lambda x: x[0] * x[1], zip(i, w_set)))
    if 1 > w or w > W:
        continue
    v = sum([sum(items[k][:j]) for j, k in zip(i, w_set)])
    if ans < v:
        ans = v

print(ans)

Submission status: Accepted

Solution code:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

N, W = map(int, input().split())
wl = [0]*N
vl = [0]*N
for i in range(N):
  wl[i], vl[i] = map(int, input().split())

dp = {}
for i in range(len(wl)):
  w, v = wl[i], vl[i]

  newdp = {}
  
  # copy
  for ew, ev in dp.items():
    if ew not in newdp:
      newdp[ew] = ev
    else:
      newdp[ew] = max(newdp[ew], ev)

    if ew + w not in newdp:
      newdp[ew+w] = ev+v
    else:
      newdp[ew+w] = max(newdp[ew+w], ev + v)

  
  if w not in newdp:
    newdp[w] = v
  else:
    newdp[w] = max(newdp[w], v)
    
  dp = newdp

ans = 0
for w, v in dp.items():
  if w <= W:
    ans = max(ans, v)
print(ans)
#print(sorted(list(dp.items())))

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import product

N, W = map(int,input().split())
w2vl = {}
lw = []

for i in range(N):
    w, v = map(int, input().split())
    lw.append(w)
    if w2vl.get(w, None) is None:
        w2vl[w] = []
    w2vl[w].append(v)
    w2vl[w] = sorted(w2vl[w],reverse=True)

ct = Counter(lw)

args = []
ws = []
for w in range(lw[0], lw[0]+4):
    if ct[w] == 0: continue
    args.append(range(ct[w]+1))
    ws.append(w)

a = 0
for i in product(*args):
    w = sum(map(lambda x: x[0] * x[1] ,zip(i,ws)))
    if 1 > w or w > W: continue
    v = sum([sum(w2vl[k][:j]) for j,k in zip(i,ws)])
    if a < v:
        a = v

print(a)

Submission status: Accepted

Solution code:
from collections import defaultdict

memo = {}
def dfs(i, w, l, W):
    if i >= len(l):
        return 0

    if (i, w) in memo:
        return memo[(i, w)]

    # not use
    ans = dfs(i + 1, w, l, W)

    # use
    if w + l[i][0] <= W:
        ans = max(ans, dfs(i + 1, w + l[i][0], l, W) + l[i][1])

    memo[(i, w)] = ans
    return ans


def main():
    N, W = map(int, input().split())
    l = []
    for _ in range(N):
        w, v = map(int, input().split())
        l.append((w, v))
    print(dfs(0, 0, l, W))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

# sys.stdin = open('d1.in')

n, W = map(int, input().split())
g = {}
w1 = 0
for i in range(n):
    w, v = map(int, input().split())
    if i == 0:
        w1 = w
        for x in range(w, w + 4):
            g[x] = []
    g[w].append(v)
for w, values in g.items():
    values.sort(reverse=True)

sg = {}
sg[w1] = {}
sg[w1 + 1] = {}
sg[w1 + 2] = {}
sg[w1 + 3] = {}
for a in range(len(g[w1]) + 1):
    sg[w1][a] = sum(g[w1][:a])
for b in range(len(g[w1 + 1]) + 1):
    sg[w1 + 1][b] = sum(g[w1 + 1][:b])
for c in range(len(g[w1 + 2]) + 1):
    sg[w1 + 2][c] = sum(g[w1 + 2][:c])
for d in range(len(g[w1 + 3]) + 1):
    sg[w1 + 3][d] = sum(g[w1 + 3][:d])

res = 0
wa = 0
for a in range(len(g[w1]) + 1):
    wa = w1 * a
    if wa > W:
        continue
    for b in range(len(g[w1 + 1]) + 1):
        wb = (w1 + 1) * b
        if wa + wb > W:
            continue
        for c in range(len(g[w1 + 2]) + 1):
            wc = (w1 + 2) * c
            if wa + wb + wc > W:
                continue
            for d in range(len(g[w1 + 3]) + 1):
                wd = (w1 + 3) * d
                if wa + wb + wc + wd > W:
                    continue
                total_w = wa + wb + wc + wd

                total_v = sg[w1][a] + sg[w1 + 1][b] + sg[w1 + 2][c] + sg[w1 + 3][d]
                if total_v > res:
                    res = total_v
print(res)

Submission status: Accepted

Solution code:
import sys

# sys.stdin = open('d1.in')

n, W = map(int, input().split())
g = {}
w1 = 0
for i in range(n):
    w, v = map(int, input().split())
    if i == 0:
        w1 = w
        for x in range(w, w + 4):
            g[x] = []
    g[w].append(v)
for w, values in g.items():
    values.sort(reverse=True)

sg = {}
sg[w1] = {}
sg[w1 + 1] = {}
sg[w1 + 2] = {}
sg[w1 + 3] = {}
for a in range(len(g[w1]) + 1):
    sg[w1][a] = sum(g[w1][:a])
for b in range(len(g[w1 + 1]) + 1):
    sg[w1 + 1][b] = sum(g[w1 + 1][:b])
for c in range(len(g[w1 + 2]) + 1):
    sg[w1 + 2][c] = sum(g[w1 + 2][:c])
for d in range(len(g[w1 + 3]) + 1):
    sg[w1 + 3][d] = sum(g[w1 + 3][:d])

res = 0
for a in range(len(g[w1]) + 1):
    for b in range(len(g[w1 + 1]) + 1):
        for c in range(len(g[w1 + 2]) + 1):
            for d in range(len(g[w1 + 3]) + 1):
                total_w = w1 * a + (w1 + 1) * b + (w1 + 2) * c + (w1 + 3) * d
                if total_w > W:
                    continue

                total_v = sg[w1][a] + sg[w1 + 1][b] + sg[w1 + 2][c] + sg[w1 + 3][d]
                if total_v > res:
                    res = total_v
print(res)

Submission status: Accepted

Solution code:
import sys

# sys.stdin = open('d1.in')

n, W = map(int, input().split())
g = {}
w1 = 0
for i in range(n):
    w, v = map(int, input().split())
    if i == 0:
        w1 = w
        for x in range(w, w + 4):
            g[x] = []
    g[w].append(v)
for w, values in g.items():
    values.sort(reverse=True)

res = 0
for a in range(len(g[w1]) + 1):
    for b in range(len(g[w1 + 1]) + 1):
        for c in range(len(g[w1 + 2]) + 1):
            for d in range(len(g[w1 + 3]) + 1):
                total_w = w1 * a + (w1 + 1) * b + (w1 + 2) * c + (w1 + 3) * d
                if total_w > W:
                    continue

                total_v = 0
                for i in range(a):
                    total_v += g[w1][i]
                for i in range(b):
                    total_v += g[w1 + 1][i]
                for i in range(c):
                    total_v += g[w1 + 2][i]
                for i in range(d):
                    total_v += g[w1 + 3][i]
                if total_v > res:
                    res = total_v
print(res)

Submission status: Accepted

Solution code:
def solve(depth, left_w):
	if depth == 4:
		return 0
	res = solve(depth+1, left_w)
	r = 0
	for vi in w4[depth]:
		left_w -= w0+depth
		if left_w < 0:
			break
		r += vi
		res = max(res, r + solve(depth+1, left_w))
	return res

n,w = map(int, raw_input().split())

w4 = [[] for i in xrange(4)]
for i in xrange(n):
	wi,vi = map(int, raw_input().split())
	if i == 0:
		w0 = wi
	w4[wi-w0].append(vi)
	
for ww in w4:
	ww.sort()
	ww.reverse()

ans = solve(0,w)
print ans

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
    w_tmp,v_tmp=map(int,input().split())
    w.append(w_tmp)
    v.append(v_tmp)

dp=[{} for _  in range(N+1)]
def rec(i,j):
    if j in dp[i] :
        return dp[i][j]
    if i==N:
         res=0
    elif j<w[i]:
        res=rec(i+1,j)
    else:
        res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i])
    dp[i][j]=res
    
    return res

print(rec(0,W))

Submission status: Accepted

Solution code:
import copy
N, W = [int(i) for i in input().split(' ')]
dic = {}
dic_num = {}
dic4calc  = {}

for i in range(N):
    new_w, new_v = [int(i) for i in input().split(' ')]
    if new_w in dic:
        dic[new_w].append(new_v)
    else:
        dic[new_w] = [new_v]
        
w = sorted(list(dic.keys()))
for wi in w:
    dic[wi].sort(reverse=True)
    dic_num[wi] = len(dic[wi])
    dic4calc[wi] = 0

cond = []
def rec(i, rest, dic4calc):
    if rest<w[i]:
        cond.append(dic4calc)
        return

    if i+1<len(w):
        new_dic4calc = copy.deepcopy(dic4calc)
        rec(i+1, rest, new_dic4calc)
    if not dic_num[w[i]]-dic4calc[w[i]]==0:
        new_dic4calc = copy.deepcopy(dic4calc)
        new_dic4calc[w[i]] += 1
        rec(i, rest-w[i], new_dic4calc)
    if i+1>=len(w):
        cond.append(dic4calc)
        return

rec(0, W, dic4calc)
ans = 0
for c in cond:
    total = 0
    for wi in w:
        total += sum(dic[wi][:c[wi]])
    if ans < total:
        ans = total
        
print(ans)