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())
wv=[ tuple([int(j) for j in input().split()]) for _ in range(N) ]
w1=wv[0][0]
w2=w1+1
w3=w1+2 
w4=w1+3

wv=sorted(wv,key=lambda x:x[1],reverse=True)
wv=sorted(wv,key=lambda x:x[0])
wvv = list(map(lambda x:x[1], wv))

# print(wv)
inf = float("inf")
ans=0
from collections import defaultdict
counter = defaultdict(int)

for i in range(N):
    w,v = wv[i]
    counter[w] += 1

from bisect import bisect_left as bll

for e1 in range(0, counter[w1]+1):
  for e2 in range(0, counter[w2]+1):
    for e3 in range(0,counter[w3]+1):
      for e4 in range(0, counter[w4]+1):
          tmp=0

          if w1*e1 + w2*e2 + w3*e3 + w4*e4 > W:
              continue

          i1=bll(wv, (w1,-inf))
          i2=bll(wv, (w2,-inf))
          i3=bll(wv, (w3,-inf))
          i4=bll(wv, (w4,-inf))

          tmp= tmp \
             +sum(wvv[i1:i1+e1])  \
             +sum(wvv[i2:i2+e2])  \
             +sum(wvv[i3:i3+e3])  \
             +sum(wvv[i4:i4+e4])

          ans=max(ans,tmp)
      
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, W = map(int, input().split())
first_item = list(map(int, input().split()))
basew = first_item[0]
w0 = []
w1 = []
w2 = []
w3 = []
w0.append(first_item[1])
for _ in range(N-1):
    w, v = map(int, input().split())
    w -= basew
    if w == 0:
        w0.append(v)
    elif w == 1:
        w1.append(v)
    elif w == 2:
        w2.append(v)
    elif w == 3:
        w3.append(v)

w0_acc = [0]+list(accumulate(sorted(w0, reverse=True)))
w1_acc = [0]+list(accumulate(sorted(w1, reverse=True)))
w2_acc = [0]+list(accumulate(sorted(w2, reverse=True)))
w3_acc = [0]+list(accumulate(sorted(w3, reverse=True)))
v = 0
for i0 in range(len(w0)+1):
    for i1 in range(len(w1)+1):
        for i2 in range(len(w2)+1):
            for i3 in range(len(w3)+1):
                if basew*(i0+i1+i2+i3)+3*i3 + 2*i2 + i1 > W:
                    break
                else:
                    v = max(v, w0_acc[i0]+w1_acc[i1]+w2_acc[i2]+w3_acc[i3])
print(v)

Submission status: Accepted

Solution code:
N, W = (int(i) for i in input().split())
w = [0]*N
v = [0]*N
for i in range(N):
  w[i], v[i] = (int(j) for j in input().split())
w0 = w[0]
wh = [a - w0 for a in w]
dp = [[[-1]*(N+1) for i in range(3*N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
  for j in range(3*N+1):
    for k in range(N+1):
      if dp[i][j][k] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
      if j - wh[i] >=0 and k-1 >=0 and dp[i][j-wh[i]][k-1] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-wh[i]][k-1]+v[i])
res = 0
for j in range(3*N+1):
  for k in range(N+1):
    if j + w0*k <= W:
      res = max(dp[N][j][k], res)
print(res)

Submission status: Accepted

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

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

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

# 各重さごとに、価値の高い順にK個とったときの価値の総和を求めておく
best_ks = {}
for w in range(w1, w + 4):
    vs = sorted(d[w], reverse=True)
    s = 0
    best_k = [0]
    for v in vs:
        s += v
        best_k.append(s)
    best_ks[w] = best_k

ans = 0
for w1_num in range(len(d[w1])+1):
    for w2_num in range(len(d[w1+1])+1):
        for w3_num in range(len(d[w1+2])+1):
            for w4_num in range(len(d[w1+3])+1):
                weight \
                    = w1_num * w1 \
                    + w2_num * (w1 + 1) \
                    + w3_num * (w1 + 2) \
                    + w4_num * (w1 + 3)
                # print(w1_num, w2_num, w3_num, w4_num, weight)
                if weight > W:
                    continue
                value \
                    = best_ks[w1][w1_num] \
                    + best_ks[w1 + 1][w2_num] \
                    + best_ks[w1 + 2][w3_num] \
                    + best_ks[w1 + 3][w4_num]
                ans = max(ans, value)
print(ans)

Submission status: Accepted

Solution code:
def solve():
  I=lambda:map(int,input().split())
  N,W=I()
  g={}
  for _ in[0]*N:
    a,b=I()
    g[a]=g.get(a,[])+[b]
  *w,=g.keys()
  v=[]
  for i in range(len(w)):
    s=[0]+sorted(g[w[i]])[::-1]
    for i in range(1,len(s)):
      s[i]+=s[i-1]
    v.append(s)
  for _ in[0]*(4-len(w)):
    w.append(10**18)
    v.append([0])
  ans=0
  for i in range(len(v[0])):
    s0=w[0]*i
    for j in range(len(v[1])):
      s1=s0+w[1]*j
      if s1>W:break
      for k in range(len(v[2])):
        s2=s1+w[2]*k
        if s2>W:break
        l=min((W-s2)//w[3],len(v[3])-1)
        ans=max(ans,v[0][i]+v[1][j]+v[2][k]+v[3][l])
  print(ans)
if __name__=='__main__':
  solve()

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()))
N,W=I()
g={}
for _ in[0]*N:
  a,b=I()
  g[a]=g.get(a,[])+[b]
*w,=g.keys()
v=[]
for i in range(len(w)):
  s=[0]+sorted(g[w[i]])[::-1]
  for i in range(1,len(s)):
    s[i]+=s[i-1]
  v.append(s)
for i in range(len(w),4):
  w.append(10**18+i)
  v.append([0,10**18])
ans=0
for i in range(len(v[0])):
  s0=w[0]*i
  for j in range(len(v[1])):
    s1=s0+w[1]*j
    if s1>W:break
    for k in range(len(v[2])):
      s2=s1+w[2]*k
      if s2>W:break
      l=min((W-s2)//w[3],len(v[3])-1)
      ans=max(ans,v[0][i]+v[1][j]+v[2][k]+v[3][l])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,ww = map(int,raw_input().split())
dic = defaultdict(list)
m = 10**20
for i in range(n):
    w,v = map(int,raw_input().split())
    m = min(w,m)
    dic[w].append(v)
mxv = 0
for i in dic:
    dic[i].sort(reverse = True)
for w in range(len(dic[m+3])+1):
    for i in range(len(dic[m+2])+1):
        for j in range(len(dic[m+1])+1):
            for k in range(len(dic[m])+1):
                tw = w*(m+3)+i*(m+2)+j*(m+1)+k*(m)
                if tw > ww:
                    continue
                else:
                    val = sum(dic[m+3][:w])+sum(dic[m+2][:i])+sum(dic[m+1][:j])+sum(dic[m][:k])
                    mxv = max(mxv,val)
print mxv

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

N,W = inpl()
H = {0: 0}
for i in range(N):
    w, v = inpl()
    for iw, iv in H.copy().items():
        if iw+w <=W:
            H[iw + w] = max(H.get(iw + w, 0),iv+v)
print(max(H.values()))

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

N,W = inpl()
H = {0: 0}
for i in range(N):
    w, v = inpl()
    for iw, iv in H.copy().items():
        if iw+w <=W:
            H[iw + w] = max(H.get(iw + w, 0),iv+v)
ans = 0
for aw,av in H.items():
    ans = max(ans,av)

print(ans)

Submission status: Accepted

Solution code:

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

w1 = []
w2 = []
w3 = []
w4 = []


for i in range(N):
    w,v = list(map(int,input().split()))
    if i==0:
        w0 = w
    
    if w==w0:
        w1.append(v)
    elif w==w0+1:
        w2.append(v)
    elif w==w0+2:
        w3.append(v)
    else:
        w4.append(v)

w1.sort()
w1=w1[::-1]

w2.sort()
w2=w2[::-1]

w3.sort()
w3=w3[::-1]

w4.sort()
w4=w4[::-1]
max_V = 0
for i1 in range(len(w1)+1):
    for i2 in range(len(w2)+1):
        for i3 in range(len(w3)+1):
            for i4 in range(len(w4)+1):
                w = i1*w0 + i2*(w0+1) + i3*(w0+2) + i4 * (w0+3)
                if w<=W:
                    V = sum(w1[:i1])+sum(w2[:i2])+sum(w3[:i3])+sum(w4[:i4])
                    max_V = max(V,max_V)

print(max_V)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, W = map(int, input().split())
dp = defaultdict(int)
dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for pw, pv in dp.copy().items():
        if pw + w <= W:
            dp[pw + w] = max(dp[pw + w], pv + v)

print(max(dp.values()))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,W = map(int, input().split())
iw,v = map(int, input().split())
d = {
    0: [v]
    ,1: []
    ,2: []
    ,3: []
}
for _ in range(1,n):
    w,v = map(int,input().split())
    d[w-iw].append(v)

for i in range(4):
    d[i] = sorted(d[i], reverse=True)

ret = -1
for i in range(min(n,len(d[0]))+1):
    if i*iw>W:
        break
    for j in range(min(n-i,len(d[1]))+1):
        if i*iw+j*(iw+1)>W:
            break
        for k in range(min(n-(i+j),len(d[2]))+1):
            if i*iw+j*(iw+1)+k*(iw+2)>W:
                break
            for l in range(min(n-(i+j+k),len(d[3]))+1):
                if i*iw+j*(iw+1)+k*(iw+2)+l*(iw+3)>W:
                    continue
                V = sum(d[0][:i])+sum(d[1][:j])+sum(d[2][:k])+sum(d[3][:l])
                ret = max(ret, V)
print(ret)

Submission status: Accepted

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

for i in range(4):
    recW[i] = sorted(recW[i], reverse=True)


a, b, c, d = len(recW[0]), len(recW[1]), len(recW[2]), len(recW[3])
recV0 = [0] * (a + 1)
for i in range(1, a + 1):
    recV0[i] = recV0[i - 1] + recW[0][i - 1][1]

recV1 = [0] * (b + 1)
for i in range(1, b + 1):
    recV1[i] = recV1[i - 1] + recW[1][i - 1][1]

recV2 = [0] * (c + 1)
for i in range(1, c + 1):
    recV2[i] = recV2[i - 1] + recW[2][i - 1][1]

recV3 = [0] * (d + 1)
for i in range(1, d + 1):
    recV3[i] = recV3[i - 1] + recW[3][i - 1][1]


num = 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):
                tmpW = W0 * i + W1 * j + W2 * k + W3 * l
                if tmpW > W:
                    continue
                else:
                    num = max(num, recV0[i] + recV1[j] + recV2[k] + recV3[l])

print(num)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, W = reads()

items = [[] for _ in range(4)]
w1, v1 = reads()
items[0].append(v1)

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

psums = []
for u in range(4):
  items[u].sort()
  items[u].reverse()
  psums.append([0] +list(accumulate(items[u])))

ans = 0
for p in product(*(range(len(items[u])+1) for u in range(4))):
  if sum((w1+u)*p[u] for u in range(4)) <= W:
    ans = max(ans, sum(psums[u][p[u]] for u in range(4)))
print(ans)

Submission status: Accepted

Solution code:
n, W = map(int, input().split())
w0, v0 = map(int, input().split())
zero = [v0]
one = []
two = []
three = []

lzero, lone, ltwo, lthree = 1, 0, 0, 0

for _ in range(n - 1):
	w, v = map(int, input().split())
	if w == w0:
		zero.append(v)
		lzero += 1
	elif w == w0 + 1:
		one.append(v)
		lone += 1
	elif w == w0 + 2:
		two.append(v)
		ltwo += 1
	else:
		three.append(v)
		lthree += 1

zero.sort(reverse=True)
one.sort(reverse=True)
two.sort(reverse=True)
three.sort(reverse=True)

zero_sum = [0]
for i in range(len(zero)):
	zero_sum.append(zero_sum[-1] + zero[i])

one_sum = [0]
for i in range(len(one)):
	one_sum.append(one_sum[-1] + one[i])

two_sum = [0]
for i in range(len(two)):
	two_sum.append(two_sum[-1] + two[i])

three_sum = [0]
for i in range(len(three)):
	three_sum.append(three_sum[-1] + three[i])

ans = 0
for i in range(lzero + 1):
	for j in range(lone + 1):
		for k in range(ltwo + 1):
			for l in range(lthree + 1):
				wei = w0 * i + (w0 + 1) * j + (w0 + 2) * k + (w0 + 3) * l
				val = zero_sum[i] + one_sum[j] + two_sum[k] + three_sum[l]
				if wei <= W and val > ans:
					ans = val

print(ans)

Submission status: Accepted

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

from collections import defaultdict
from itertools import accumulate

cs = defaultdict(list)

for w, v in WV:
    cs[w].append(v)

minw = min(cs.keys())

for k in range(minw, minw+4):
    cs[k] = [0] + list(accumulate(sorted(cs[k], reverse=True)))

result = 0

for w0, t0 in enumerate(cs[minw]):
    for w1, t1 in enumerate(cs[minw+1]):
        tw1 = w0 * minw + w1 * (minw+1)
        tv1 = t0 + t1
        if tw1 > W:
            break
        for w2, t2 in enumerate(cs[minw+2]):
            tw2 = tw1 + w2 * (minw+2)
            tv2 = tv1 + t2
            if tw2 > W:
                break
            for w3, t3 in enumerate(cs[minw+3]):
                tw3 = tw2 + w3 * (minw+3)
                tv3 = tv2 + t3
                if tw3 > W:
                    break
                result = max(result, tv3)

print(result)

Submission status: Accepted

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

def solve(N, W, WV):
    if N == 0:
        return 0
    if W == 0:
        return 0

from collections import defaultdict
from itertools import accumulate

cs = defaultdict(list)

for w, v in WV:
    cs[w].append(v)

minw = min(cs.keys())

for k in range(minw, minw+4):
    cs[k] = [0] + list(accumulate(sorted(cs[k], reverse=True)))

ts = defaultdict(int)

result = solve(N, W, WV)
result = 0

for w1, t1 in enumerate(cs[minw]):
    for w2, t2 in enumerate(cs[minw+1]):
        tw2 = w1 * minw + w2 * (minw+1)
        tv2 = t1 + t2
        if tw2 > W:
            break
        for w3, t3 in enumerate(cs[minw+2]):
            tw3 = tw2 + w3 * (minw+2)
            tv3 = tv2 + t3
            if tw3 > W:
                break
            for w4, t4 in enumerate(cs[minw+3]):
                tw4 = tw3 + w4 * (minw+3)
                tv4 = tv3 + t4
                # print(w1, w2, w3, w4, tv4)
                if tw4 > W:
                    break
                result = max(result, tv4)

print(result)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, W] =  [long(input_raw[0]), long(input_raw[1])]
    v = []
    item = {}
    v_sum = {}
    for i in range(N):
        input_raw = read_func().strip().split()
        [wi, vi] =  [long(input_raw[0]), long(input_raw[1])]
        if wi not in item:
            item[wi] = [vi]
        else:
            item[wi].append(vi)

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

    w_list = []
    for wi in item:
        item[wi].sort(reverse = True)
        w_list.append(wi)
        v_sum[wi] = [0L for i in range(len(item[wi]) + 1)]
        v_sum[wi][1] = item[wi][0]
        for i in range(1, len(item[wi])):
            v_sum[wi][i + 1] = v_sum[wi][i] + item[wi][i]

    max_value = 0L
    for i in range(len(item[w_list[0]]) + 1):
        for j in range(len(item[w_list[1]]) + 1):
            for k in range(len(item[w_list[2]]) + 1):
                for l in range(len(item[w_list[3]]) + 1):
                    if W - (i * max(0L, w_list[0]) + j * max(0L, w_list[1]) + k * max(0L, w_list[2]) + l * max(0L, w_list[3])) >= 0:
                        value = v_sum[w_list[0]][i] + v_sum[w_list[1]][j] + v_sum[w_list[2]][k] + v_sum[w_list[3]][l]
                        if max_value < value:
                            max_value = value
    print max_value

##    W_ = long(N * 4 + 1)
##    dp = [[0L for j in range((W_) + 1)] for i in range(N + 1)]
##
##    for i in range(N):
##        for j in range(W_ + 1):
##
##            k = ((j - 1)%4 +  ((j - 1)/4 +1) * w[0]) - w[i]
##            #print k, j, w[i]
##            if k  < 0 or j == 0:
##                dp[i + 1][j] = dp[i][j]
##            else:
##                if k >= w[0]:
##                    l = k / w[0] + 3 * (k / w[0] - 1)
##                else:
##                    l = 0
##                print i ,w[i], k, l
##                dp[i + 1][j] = max(dp[i][j], dp[i][l] + v[i])
##
##    maximum = 0
##    for i in range(1, W_ + 1):
##        if maximum < dp[N][i] and (i - 1)%4 +  ((i - 1)/4 +1) * w[0] <= W:
##            maximum = dp[N][i]
##
##    print maximum


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    w, v = [], []
    for i in range(N):
        wi, vi = map(int, input().split())
        w.append(wi)
        v.append(vi)

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

    ans = 0
    for i in range(N+1):
        for j in range(3*i+1):
            ans = max(ans, dp[N][i][j])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
table=[[] for i in range(4)]
a,b = map(int,input().split())
table[0].append(b)
for i in range(1,N):
    w,v = map(int,input().split())
    table[w-a].append(v)
for i in range(4):
    table[i].sort()
    table[i]+=[0]
ans=0
for i in range(len(table[3])+1):
    for j in range(len(table[1])+1):
        for k in range(len(table[2])+1):
            t=(W-a*(i+j+k)-j-2*k-3*i)//a
            if t<0:
                break
            else:
                x=sum(table[3][-i-1:]+table[1][-j-1:]+table[2][-k-1:]+table[0][-t-1:])
                ans=max(ans,x)  
print(ans)

Submission status: Accepted

Solution code:
ints = input().split(" ")
N = int(ints[0])
maxW = int(ints[1])
ints = input().split(" ")
a = int(ints[0])
b = int(ints[1])
weight = [a, a+1, a+2, a+3] 
va = [[b],[],[],[]]
for i in range(1, N):
	ins = input().split(" ")
	w = int(ins[0])
	v = int(ins[1])
	for j in range(0, 4):
		if w == weight[j]:
			va[j].append(v)
for i in range(0, len(va)):
	va[i].sort(reverse=True)
	va[i].insert(0,0)
#print(va)
sum = [[0],[0],[0],[0]]
for j in range(0, 4):
	for i in range(1, len(va[j])):
		try:
			sum[j].append(sum[j][i-1] + va[j][i])
		except:
			pass
ans = 0
#print(sum)
for i in range(0, len(va[0])):
	for j in range(0, len(va[1])):
		for k in range(0, len(va[2])):
			for l in range(0, len(va[3])):
				sumw = weight[0]*i + weight[1]*j +weight[2]*k + weight[3]*l
				if(sumw <= maxW):
					ans = max(sum[0][i]+sum[1][j]+sum[2][k]+sum[3][l],ans)
print(ans)

Submission status: Accepted

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

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

w0, v0 = list(map(int, input().split()))
values[0].append(v0)

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

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

res = 0

for i1 in range(len(values[0])+1):
    for i2 in range(len(values[1])+1):
        for i3 in range(len(values[2])+1):
            for i4 in range(len(values[3])+1):
                if(w0*i1 + (w0+1)*i2 + (w0+2)*i3 + (w0+3)*i4 <= W):
                    res = max(res, values[0][i1-1] + values[1][i2-1] + values[2][i3-1] + values[3][i4-1])

print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from itertools import accumulate, product
 
N, W = inpl()
A = []
for _ in range(N):
    A.append(inpl())
B = [[] for _ in range(4)]
w1 = A[0][0]
 
for w, v in A:
    B[w-w1].append(v)
 
B = [sorted(b, reverse=True) for b in B]
C = [[0] + list(accumulate(b)) for b in B]
 
res = 0

for L in product(enumerate(C[0]),
                 enumerate(C[1]),
                 enumerate(C[2]),
                 enumerate(C[3])):
    if sum([(w1+i)*l[0] for i, l in enumerate(L)]) <= W:
        res = max(res, sum([l[1] for l in L]))

print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import accumulate, product
from operator import itemgetter

def inpl(): return tuple(map(int, input().split()))
N, W = inpl()
I = [inpl() for _ in range(N)]
w1 = I[0][0]
A = {w1 + x: [] for x in range(4)}

for w, v in I:
    A[w].append(v)

for k, v in A.items():
    A[k] = [0] + list(accumulate(sorted(v, reverse=True)))

res = 0
g0 = itemgetter(0)
g1 = itemgetter(1)

for L in product(enumerate(A[w1]),
                 enumerate(A[w1+1]),
                 enumerate(A[w1+2]),
                 enumerate(A[w1+3])):
    if sum([(w1+i)*l for i, l in enumerate(map(g0, L))]) <= W:
        res = max(res, sum(map(g1, L)))

print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import accumulate, product

def inpl(): return tuple(map(int, input().split()))
N, W = inpl()
I = [inpl() for _ in range(N)]
w1 = I[0][0]
A = {w1 + x: [] for x in range(4)}

for w, v in I:
    A[w].append(v)

for k, v in A.items():
    A[k] = [0] + list(accumulate(sorted(v, reverse=True)))

res = 0

for L in product(enumerate(A[w1]),
                 enumerate(A[w1+1]),
                 enumerate(A[w1+2]),
                 enumerate(A[w1+3])):
    if sum([(w1+i)*l[0] for i, l in enumerate(L)]) <= W:
        res = max(res, sum([l[1] for l in L]))

print(res)

Submission status: Accepted

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

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

ws = []
vs = []

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

dp = [{} for i in range(N)]
dp[0][ws[0]] = vs[0]
dp[0][0] = 0

for i in range(1,N):
    tmp = dp[i-1].copy()
    for key, value in tmp.items():
        dp[i].setdefault(ws[i]+key, 0)
        dp[i].setdefault(key, 0)
        #print(i, key, value, value+vs[i], dp[i][ws[i]+key])
        dp[i][ws[i]+key] = max(value+vs[i], dp[i][ws[i]+key])
        dp[i][key] = max(value,dp[i][key])

max_value = 0
for i in range(N):
    tmp = []
    for key, value in dp[i].items():
        if key <= W:
            tmp.append(value)
    if len(tmp)!=0:
        max_value = max(max_value, max(tmp))

#print(dp)
print(max_value)

Submission status: Accepted

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

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

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

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

res = 0

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())  # N<=100, W<=10**9
w, v = [0] * N, [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())  # すべての i=2,3,…,N について、w1 ≦ wi ≦ w1+3

#

def kaihou():
    monos_by_omosa = [[] for _ in range(4)]
    w0 = w[0]
    for i in range(N):
        monos_by_omosa[w[i] - w0].append(v[i])
    for i in range(4):
        monos_by_omosa[i].sort()
        monos_by_omosa[i].reverse()
    # print(monos_by_omosa)
    ans = 0
    for i in range(N + 1):
        if i > len(monos_by_omosa[0]):
            break
        w0i = (w0) * i
        if w0i > W:
            break

        for j in range(N + 1 - i):
            if j > len(monos_by_omosa[1]):
                break
            w1j = (w0 + 1) * j
            if w0i + w1j > W:
                break

            for k in range(N + 1 - i - j):
                if k > len(monos_by_omosa[2]):
                    break
                w2k  = (w0 + 2) * k
                if w0i + w1j + w2k > W:
                    break

                for l in range(N + 1 - i - j - k):
                    if l > len(monos_by_omosa[3]):
                        break
                    w3l = (w0 + 3) * l
                    if w0i + w1j + w2k + w3l > W:
                        break

                    val = sum(monos_by_omosa[0][:i])
                    val += sum(monos_by_omosa[1][:j])
                    val += sum(monos_by_omosa[2][:k])
                    val += sum(monos_by_omosa[3][:l])
                    ans = max(ans, val)
    return ans

print(kaihou())

Submission status: Accepted

Solution code:
N, W = map(int, input().split())  # N<=100, W<=10**9
w, v = [0] * N, [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())  # すべての i=2,3,…,N について、w1 ≦ wi ≦ w1+3

#

def kaihou():
    monos_by_omosa = [[] for _ in range(4)]
    w0 = w[0]
    for i in range(N):
        monos_by_omosa[w[i] - w0].append(v[i])
    for i in range(4):
        monos_by_omosa[i].sort()
        monos_by_omosa[i].reverse()
    # print(monos_by_omosa)
    ans = 0
    for i in range(N + 1):
        if i > len(monos_by_omosa[0]):
            break
        w0i = (w0) * i
        if w0i > W:
            break

        for j in range(N + 1 - i):
            if j > len(monos_by_omosa[1]):
                break
            w1j = (w0 + 1) * j
            if w0i + w1j > W:
                break

            for k in range(N + 1 - i - j):
                if k > len(monos_by_omosa[2]):
                    break
                w2k  = (w0 + 2) * k
                if w0i + w1j + w2k > W:
                    break

                for l in range(N + 1 - i - j - k):
                    if l > len(monos_by_omosa[3]):
                        break
                    w3l = (w0 + 3) * l
                    if w0i + w1j + w2k + w3l > W:
                        break

                    val = sum(monos_by_omosa[0][:i])
                    val += sum(monos_by_omosa[1][:j])
                    val += sum(monos_by_omosa[2][:k])
                    val += sum(monos_by_omosa[3][:l])
                    ans = max(ans, val)
    return ans

print(kaihou())

Submission status: Accepted

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

def rec(i, j):
    if (i, j) in dp:
        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


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

dp = {}
print(rec(0, W))

Submission status: Accepted

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

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

from collections import defaultdict
dp = defaultdict(int) # w -> v
dp[0] = 0

for w,v in items:
  for tw,tv in list(dp.items()):
    if tw+w <= W:
      dp[tw+w] = max(tv+v, dp[tw+w])

print(max(dp.values()))

Submission status: Accepted

Solution code:
from itertools import izip


def sol(n, w, wis, vis):
    rv = 0
    w1 = wis[0]
    coll = [[] for _ in xrange(n)]
    for wi, vi in izip(wis, vis):
        coll[wi - w1].append(vi)
    coll = map(lambda x: sorted(x, reverse=True), coll)
    lis = map(len, coll)
    for k1 in xrange(min(lis[0] + 1, n + 1)):
        for k2 in xrange(min(lis[1] + 1, n + 1 - k1)):
            for k3 in xrange(min(lis[2] + 1, n + 1 - k1 - k2)):
                for k4 in xrange(min(lis[3] + 1, n + 1 - k1 - k2 - k3)):
                    kis = [k1, k2, k3, k4]
                    if sum([(w1 + i) * kis[i] for i in xrange(4)]) > w:
                        continue
                    rv = max(rv, sum([sum(coll[i][:kis[i]]) for i in xrange(4)]))

    return rv


if __name__ == "__main__":
    n, w = map(int, raw_input().strip().split())
    wis, vis = [], []
    for _ in xrange(n):
        wi, vi = map(int, raw_input().strip().split())
        wis.append(wi)
        vis.append(vi)
    print(sol(n, w, wis, vis))

Submission status: Accepted

Solution code:
from itertools import product, accumulate

n, w = map(int, input().split())
w1, v1 = map(int, input().split())
packages = [[v1], [], [], []]
for _ in range(n - 1):
    wi, vi = map(int, input().split())
    packages[wi - w1].append(vi)
for ofs, lst in enumerate(packages):
    lst.sort(reverse=True)
    packages[ofs] = list(accumulate([0] + lst))

tmp_max = 0
for a, b, c, d in product(*(range(len(packages[ofs])) for ofs in range(4))):
    if w1 * (a + b + c + d) + b + 2 * c + 3 * d > w:
        continue
    tmp_max = max(tmp_max, sum(packages[ofs][m] for ofs, m in zip(range(4), (a, b, c, d))))
print(tmp_max)

Submission status: Accepted

Solution code:
from copy import deepcopy

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

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

print( max( map( max, dp ) ) )

Submission status: Accepted

Solution code:
n,W=map(int,raw_input().split())
wv=[map(int,raw_input().split()) for _ in xrange(n)]
diff=[[0] for _ in xrange(4)]
for i in xrange(n):
    w,v=wv[i]
    diff[w-wv[0][0]].append(v)
for i in xrange(4):
    diff[i].sort(reverse=True)
ans=0
for i in xrange(len(diff[0])):
    for j in xrange(len(diff[1])):
        for k in xrange(len(diff[2])):
            for l in xrange(len(diff[3])):
                if wv[0][0]*(i+j+k+l)+(j+2*k+3*l)<=W:
                    ans=max(ans,sum(diff[0][0:i])+sum(diff[1][0:j])+sum(diff[2][0:k])+sum(diff[3][0:l]))
print ans