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:
# -*- coding: utf-8 -*-
import sys
from itertools import accumulate 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

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

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

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

Submission status: Accepted

Solution code:
N , W = map(int,input().split())
mono = [tuple(map(int,input().split())) for i in range(N)]
w1 = mono[0][0]
dp = [[-1 for i in range(301)] for j in range(N+1)]
dp[0][0] = 0 

for i in range(N):
    p = mono[i][0] - w1
    for j in reversed(range(N)):
        for k in reversed(range(301)):
            if dp[j][k] != -1:
                dp[j+1][k+p] = max(dp[j+1][k+p],dp[j][k]+mono[i][1])

ans = 0
for i in range(N+1):
    for j in range(301):
        if i*w1 + j <= W:
            ans = max(ans,dp[i][j])

print(ans)

Submission status: Accepted

Solution code:
# 普通のナップサックは O(荷物の数、ナップサックに入る重量の上限)で計算できる。
# 今回はこれだと O(100 * 10**9) なので無理。
# 明らかに条件で重要なのは「すべてのi=2,3,...,Nについて、w_1<=w_i<=w_1+3」

# w_1が1000とする
# W = 4500→4つが必ず入り、5つは必ず入らない。価値の高いものから4つ。
# W = 4005→3つが必ず入る。4つが入るかどうかは場合による。
# max(3つの場合, 4つの場合)。3つは価値の高いものから3つ。4つは?
# 4つ選ぶ、4005以下、価値最大化
# dp[i][k][l]

# w_1〜w_iの中からk個選んで、重量をちょうどlにしたときの、最大価値
# dp[i][k][l] := max(dp[i-1][k][l], dp[i-1][k-1][l - w_i] + v_i)

# w_1〜w_iの中からk個選んで、重量をl以下にしたときの、最大価値
# dp[i][k][l] := max(dp[i-1][k][l], dp[i-1][k-1][l - w_i] + v_i)

# 後者を使うべき。更新式は同じで最後に重量に関してmaxを取る手間が無いので。
# i <= N, k <= N, l <= 3*N

n, w_limit = list(map(int, input().split()))

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

weight_base = baggage[0][0]

# i添字は0〜n-1 問題文から1引いて0-indexにする
# k添字は0〜n 
# l添字は0〜3n

for i in range(n):
    baggage[i][0] -= weight_base

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

for l in range(baggage[0][0], 3*n):
    dp[0][1][l] = baggage[0][1]

for i in range(1, n):
    for k in range(1, n+1):
        for l in range(3*n+1):
            if l - baggage[i][0] >= 0:
                dp[i][k][l] = max(dp[i-1][k][l], dp[i-1][k-1][l - baggage[i][0]] + baggage[i][1])
            else:
                dp[i][k][l] = dp[i-1][k][l]

valid_min_num = w_limit // (weight_base+3)
valid_max_num = w_limit // weight_base

ans = 0
for num in range(valid_min_num, min(valid_max_num, n) + 1):
    weight_rest = w_limit - weight_base * num
    if weight_rest >= 3*n:
        weight_rest = 3*n

    # print(n-1, num, weight_rest)
    ans = max(ans, dp[n-1][num][weight_rest])

print(ans)

Submission status: Accepted

Solution code:
# 普通のナップサックは O(荷物の数、ナップサックに入る重量の上限)で計算できる。
# 今回はこれだと O(100 * 10**9) なので無理。
# 明らかに条件で重要なのは「すべてのi=2,3,...,Nについて、w_1<=w_i<=w_1+3」

# w_1が1000とする
# W = 4500→4つが必ず入り、5つは必ず入らない。価値の高いものから4つ。
# W = 4005→3つが必ず入る。4つが入るかどうかは場合による。
# max(3つの場合, 4つの場合)。3つは価値の高いものから3つ。4つは?
# 4つ選ぶ、4005以下、価値最大化
# dp[i][k][l]

# w_1〜w_iの中からk個選んで、重量をちょうどlにしたときの、最大価値
# dp[i][k][l] := max(dp[i-1][k][l], dp[i-1][k-1][l - w_i] + v_i)

# w_1〜w_iの中からk個選んで、重量をl以下にしたときの、最大価値
# dp[i][k][l] := max(dp[i-1][k][l], dp[i-1][k-1][l - w_i] + v_i)

# 後者を使うべき。更新式は同じで最後に重量に関してmaxを取る手間が無いので。
# i <= N, k <= N, l <= 3*N

n, w_limit = list(map(int, input().split()))

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

weight_base = baggage[0][0]

# i添字は0〜n-1 問題文から1引いて0-indexにする
# k添字は0〜n 
# l添字は0〜3n

for i in range(n):
    baggage[i][0] -= weight_base

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

for l in range(baggage[0][0], 3*n):
    dp[0][1][l] = baggage[0][1]

for i in range(1, n):
    for k in range(1, n+1):
        for l in range(3*n+1):
            if l - baggage[i][0] >= 0:
                dp[i][k][l] = max(dp[i-1][k][l], dp[i-1][k-1][l - baggage[i][0]] + baggage[i][1])
            else:
                dp[i][k][l] = dp[i-1][k][l]

valid_min_num = w_limit // (weight_base+3)
valid_max_num = w_limit // weight_base

ans = 0
for num in range(valid_min_num, min(valid_max_num, n) + 1):
    weight_rest = w_limit - weight_base * num
    if not 0 <= weight_rest:  # ここがないとREになるらしい。理由を要検討。
        continue
    elif weight_rest >= 3*n:
        weight_rest = 3*n

    # print(n-1, num, weight_rest)
    ans = max(ans, dp[n-1][num][weight_rest])

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()
offset = 10**10

def main():
    """
    ナップサックで重さを飛び飛びにしてdpを軽くしなくても、
    そもそも重さが４パターンだから全探索で解けたのか。。。。。。
    """
    N, W = map(int, input().split())
    item = [[] for _ in range(4)]
    length = [1, 0, 0, 0]
    w0, v0 = map(int, input().split())
    item[0].append(v0)
    for _ in range(N - 1):
        w, v = map(int, input().split())
        item[w - w0].append(v)
        length[w - w0] += 1
    for i in range(4): item[i].sort(reverse=True)

    # 重さの累積和
    S = []
    for i in range(4):
        S.append([0] + list(accumulate(item[i])))

    ans = 0
    for a in range(length[0] + 1):
        for b in range(length[1] + 1):
            for c in range(length[2] + 1):
                for d in range(length[3] + 1):
                    weight = a * w0 + b * (w0 + 1) + c * (w0 + 2) + d * (w0 + 3)
                    if weight > W: continue
                    ans = max(ans, S[0][a] + S[1][b] + S[2][c] + S[3][d])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
offset = 10**10

def main():
    N, W = map(int, input().split())
    w0, v0 = map(int, input().split())
    item = [0, w0 * offset + v0]
    weight_sum, value_sum = w0, v0
    for _ in range(1, N):
        w, v = map(int, input().split())
        item.append(w * offset + v)
        weight_sum += w
        value_sum += v

    if W < w0:
        print(0)
        return
    if weight_sum <= W:
        print(value_sum)
        return

    if w0 <= 3 * (N - 1):
        # dp[i][j] = (1~i番目の荷物を重さj以下で詰めたときの最大価値)
        dp = [[0] * (W + 1) for _ in range(N + 1)]
        for i in range(1, N + 1):
            w, v = item[i] // offset, item[i] % offset
            for j in range(w): dp[i][j] = dp[i - 1][j]
            for j in range(w, W + 1):
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
        print(dp[N][W])
        return

    # dp[i][j][k] = (1~i番目までのものを見たとき、重さが(j * w0 + k)以下で最大価値がいくらか)
    dp = [[[0] * (3 * (N - 1) + 1) for _ in range(N + 1)] for _ in range(N + 1)]
    for i in range(1, N + 1):
        w, v = item[i] // offset, item[i] % offset
        for j in range(i + 1):
            for k in range(3 * (N - 1) + 1):
                weight = j * w0 + k
                q, r = (weight - w) // w0, (weight - w) % w0
                if weight < w:
                    dp[i][j][k] = dp[i - 1][j][k]
                elif (weight - w) % w0 > 3 * (N - 1):
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][q][3 * (N - 1)] + v)
                else:
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][q][r] + v)
    q, r = W // w0, min(W % w0, 3 * (N - 1))
    print(dp[N][q][r])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
x1,y1=map(int,input().split())
d={x1:[y1],x1+1:[],x1+2:[],x1+3:[]}
for _ in range(n-1):
    x,y=map(int,input().split())
    d[x].append(y)
d={k:[0]+sorted(d[k],reverse=True) for k in d}
vm=0
v1,w1=0,0
for e in d[x1]:
    v1+=e
    w1+=0 if e==0 else x1
    v2,w2=0,0
    for f in d[x1+1]:
        v2+=f
        w2+=0 if f==0 else x1+1
        v3,w3=0,0
        for g in d[x1+2]:
            v3+=g
            w3+=0 if g==0 else x1+2
            v4,w4=0,0
            for h in d[x1+3]:
                v4+=h
                w4+=0 if h==0 else x1+3
                ws=w1+w2+w3+w4
                vs=v1+v2+v3+v4
                if ws<=w:
                    vm=max(vm,vs)
print(vm)

Submission status: Accepted

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

dp={0:0}

for cw,cv in gds:
    tmp={}

    for key,value in dp.items():
        if key in tmp:
            tmp[key]=max(tmp[key],value)
        else:
            tmp[key]=value
        
        if cw+key<=w:
            if cw+key in tmp:
                tmp[cw+key]=max(tmp[cw+key],value+cv)
            else:
                tmp[cw+key]=value+cv
    
    dp=tmp

print(max(dp.values()))

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
wv = []
base_w = float('inf')
for _ in range(N):
    w, v = (int(x) for x in input().split())
    wv.append([w, v])
    base_w = min(base_w, w)

dp = [[-10000000000 for i in range(100*3+1)] for j in range(N+1)]

dp[0][0] = 0

#横軸はお重さの合計、縦軸は何個選ぶか
for ws ,vs in wv:
    ws -= base_w
    for h in range(N+1, 0, -1):
        for w in range(100*3, -1, -1):
            if 0 <= w-ws:
                if dp[h-1][w-ws] != -10000000000:
                    dp[h][w] = max(dp[h][w], dp[h-1][w-ws]+vs)

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
  wi, vi = map(int, input().split())
  w.append(wi)
  v.append(vi)

V = [[], [], [], []]
for wi, vi in zip(w, v):
  V[wi - w[0]].append(vi)

for vv in V:
  vv.sort(reverse=True)

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

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
dp=[[-1]*301 for i in range(N+1)]
dp[0][0]=0

for i in range(N):
    w,v=map(int,input().split())
    if i==0:
        base=w
    for i in range(N)[::-1]:
        for j in range(301)[::-1]:
            if dp[i][j]!=-1:
                dp[i+1][j+w-base]=max(dp[i][j]+v,dp[i+1][j+w-base])

ans=0
for index,item in enumerate(dp):
    if W-index*base+1<=0:
        break
    ans=max(max(item[:W-index*base+1]),ans)

print(ans)

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
import collections
dic = collections.defaultdict(list)
w_min = float('inf')
for _ in range(n):
    a,b = map(int,input().split())
    dic[a].append(b)
    dic[a].sort(reverse = True)
    w_min = min(w_min,a)

sum_dic = collections.defaultdict(list)
for key,li in dic.items():
    if len(sum_dic[key])==0:
        sum_dic[key].append(0)
    for l in li:
        sum_dic[key].append(sum_dic[key][-1] + l)
ans = 0

for i in range(4):
    if len(sum_dic[w_min+i])==0:
        sum_dic[w_min+i].append(0)

for i,v1 in enumerate(sum_dic[w_min]):
        for j,v2 in enumerate(sum_dic[w_min+1]):
            for k,v3 in enumerate(sum_dic[w_min+2]):
                for l,v4 in enumerate(sum_dic[w_min+3]):
                    if (i+j+k+l)*w_min + j+2*k+3*l<=w:
                        ans = max(ans,v1+v2+v3+v4)
print(ans)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,W = MI()
w1,v = MI()
v0,v1,v2,v3 = [v],[],[],[]  # 重さが w1,w1+1,w1+2,w1+3 である荷物の価値
for i in range(N-1):
    w,v = MI()
    if w == w1:
        v0.append(v)
    elif w == w1+1:
        v1.append(v)
    elif w == w1+2:
        v2.append(v)
    else:
        v3.append(v)

v0.sort(reverse=True)
v1.sort(reverse=True)
v2.sort(reverse=True)
v3.sort(reverse=True)
N0,N1,N2,N3 = len(v0),len(v1),len(v2),len(v3)

from itertools import accumulate
v0_accumulate = [0] + list(accumulate(v0))
v1_accumulate = [0] + list(accumulate(v1))
v2_accumulate = [0] + list(accumulate(v2))
v3_accumulate = [0] + list(accumulate(v3))

ans = 0
for i in range(N0+1):  # 重さが w1 である荷物を i 個選ぶ
    for j in range(N1+1):  # 重さが w1+1 である荷物を j 個選ぶ
        for k in range(N2+1):  # 重さが w1+2 である荷物を k 個選ぶ
            for l in range(N3+1):  # 重さが w1+3 である荷物を l 個選ぶ
                if w1*i + (w1+1)*j + (w1+2)*k + (w1+3)*l <= W:
                    ans = max(ans,v0_accumulate[i]+v1_accumulate[j]+v2_accumulate[k]+v3_accumulate[l])
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, W, *wv = map(int, read().split())

    w0 = wv[0]
    weight = [[] for _ in range(4)]
    for w, v in zip(*[iter(wv)] * 2):
        weight[w - w0].append(v)

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

    csum = [[0] for _ in range(4)]
    for i in range(4):
        csum[i].extend(accumulate(weight[i]))

    def dfs(w, v, idx):
        if idx == 4:
            return v

        ans = 0
        for i in range(len(csum[idx])):
            if w + (w0 + idx) * i > W:
                break
            ans = max(ans, dfs(w + (w0 + idx) * i, v + csum[idx][i], idx + 1))

        return ans

    print(dfs(0, 0, 0))

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def solve1(N, W, weight, value):
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        for w in range(W + 1):
            if w - weight[i] >= 0:
                dp[i + 1][w] = dp[i][w - weight[i]] + value[i]
            if dp[i + 1][w] < dp[i][w]:
                dp[i + 1][w] = dp[i][w]

    return dp[N][W]


def solve2(N, W, weight, value):
    w0 = weight[0]
    M = W // w0
    if M == 0:
        return 0

    weight_adj = [w - w0 for w in weight]
    w_total = sum(weight_adj)

    dp = [[[0] * (w_total + 1) for j in range(N + 1)] for i in range(M + 1)]
    for i in range(M):
        for j in range(N):
            for w in range(w_total + 1):
                if w - weight_adj[j] >= 0:
                    dp[i + 1][j + 1][w] = dp[i][j][w - weight_adj[j]] + value[j]
                if dp[i + 1][j + 1][w] < dp[i + 1][j][w]:
                    dp[i + 1][j + 1][w] = dp[i + 1][j][w]
                if dp[i + 1][j + 1][w] < dp[i][j + 1][w]:
                    dp[i + 1][j + 1][w] = dp[i][j + 1][w]

    return max(dp[M][N][min(W - w0 * M, w_total)], dp[M - 1][N][min(W - w0 * (M - 1), w_total)])


def main():
    N, W, *wv = map(int, read().split())
    weight = wv[::2]
    value = wv[1::2]

    if weight[0] < 500:
        ans = solve1(N, W, weight, value)
    else:
        ans = solve2(N, W, weight, value)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np

def main():
    def itrsum(arr):
        n=len(arr)
        tri=np.array([[i>=j for i in range(n)] for j in range(n+1)])
        return np.dot(tri,arr).astype('int64')
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    # arr=[sorted([x for x in t if x[0]==w1+i],reverse=True,key=lambda e:e[1]) for i in range(4)]
    arr=[[x for x in t if x[0]==w1+i] for i in range(4)]
    arr=[l for l in arr]
    lenarr=list(map(len,arr))
    arr0=[itrsum(np.array(sorted([x[0] for x in l]),dtype='int64')) for l in arr]
    arr1=[itrsum(np.array(sorted([x[1] for x in l]),dtype='int64')) for l in arr]
    # arr=[x.sort(reverse=True,key=lambda e:e[1]) for x in arr]
    arr=np.array(arr)
    arrw=0
    arrv=0
    for i in range(4):
        arrw=np.ravel(arr0[i].reshape(lenarr[i]+1,1)+np.array([arrw]))
        arrv=np.ravel(arr1[i].reshape(lenarr[i]+1,1)+np.array([arrv]))
    #print(arr0)
    #print(arr1)
    #print('\n')
    #print(arrw)
    #print(arrv)
    #print(arrv[arrw<=w])
    ansarr=arrv[arrw<=w]
    print(np.max(ansarr))
    # wts=list(map(lambda l:l[0]-w1-1, t))
    # val=list(map(lambda l:l[1], t))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
N,W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
DP = defaultdict(int)
DP[0] = 0
for weight, value in wv:
  exists = list(DP.items())
  for key, total in exists:
    new_key = key + weight
    if new_key > W:
      continue
    new_total = total + value
    if DP[new_key] < new_total:
      DP[new_key] = new_total

print(max(DP.values()))

Submission status: Accepted

Solution code:
N,W = map(int,input().rstrip().split(" "))
DP = [[-1 for _ in range(310)] for _ in range(N+1)]
DP[0][0] = 0
ans = 0
for i in range(N):
    w,v = map(int,input().rstrip().split(" "))
    if i == 0: w1 = w
    for i2 in range(i,-1,-1):
        for i3 in range(309,-1,-1):
            if DP[i2][i3] != -1:
                DP[i2 + 1][i3 + (w - w1)] = max(DP[i2 + 1][i3 + (w - w1)],DP[i2][i3]+v)
                if i2 * w1 + i3 + w <= W:
                    ans = max(DP[i2 + 1][i3 + (w - w1)],ans)
print(ans)

Submission status: Accepted

Solution code:
import copy

N, W = map(int, input().split())
wvl = []
first_w, v = map(int, input().split())
wvl.append((first_w,v))
for _ in range(N-1):
    w,v = map(int, input().split())
    # wvl.append((w-first_w,v))
    wvl.append((w,v))

w_set_res = set()
w_set = set()
w_set_res.add(0)
w_set.add(0)
for i in range(N-1):
    next_w_set = set()
    for w in list(w_set):
        for j in range(0,4):
            new_w = w+j+first_w
            if new_w <= W:
                next_w_set.add(new_w)
                w_set_res.add(new_w)
    w_set = copy.deepcopy(next_w_set)

w_set_res.add(0)
# print(w_set_res)
w_list = list(w_set_res)
w_list.sort()

max_w = min(4*N, W-first_w*N)
dp = [ {0:0} for _ in range(N+1)]
for d in dp:
    for w in w_list:
        d[w] = 0

for i in range(N):
    wi,vi = wvl[i]
    for w in w_list:
        if w-wi in w_set_res:
            dp[i+1][w] = max(dp[i][w-wi] + vi, dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

# print(dp)
print(max(dp[N].values()))

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
A=[]
W1,W2,W3,W4=[],[],[],[]
for i in range(N):
  w,v=map(int,input().split())
  if i==0:
    a=w
  A.append((v,w))
  if w-a==0:
    W1.append(v)
  elif w-a==1:
    W2.append(v)
  elif w-a==2:
    W3.append(v)
  else:
    W4.append(v)
  

W1,W2,W3,W4=sorted(W1)[::-1],sorted(W2)[::-1],sorted(W3)[::-1],sorted(W4)[::-1]

l1,l2,l3,l4=len(W1),len(W2),len(W3),len(W4)
ans=0
for i in range(l1+1):
  for j in range(l2+1):
    for k in range(l3+1):
      for l in range(l4+1):
        value=sum(W1[:i])+sum(W2[:j])+sum(W3[:k])+sum(W4[:l])
        if a*i+(a+1)*j+(a+2)*k+(a+3)*l<=W:
          ans=max(ans,value)
print(ans)

Submission status: Accepted

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

minw = min(w)
for i in range(N):
    w[i] -= minw

ww = [[] for _ in range(4)]
for i, o in enumerate(w):
    ww[o].append(v[i])
for i in range(4):
    ww[i].sort(reverse=True)

ans = 0
for i in range(len(ww[0])+1):
    isum = sum(ww[0][:i])
    for j in range(len(ww[1])+1):
        jsum = sum(ww[1][:j])
        for k in range(len(ww[2])+1):
            ksum = sum(ww[2][:k])
            for t in range(len(ww[3])+1):
                tsum = sum(ww[3][:t])
                weight = minw * i + (minw+1) * j + (minw+2) * k + (minw+3) * t
                if weight <= W:
                    ans = max(ans, isum+jsum+ksum+tsum)
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = []
w0 = []
w1 = []
w2 = []
w3 = []
for i in range(N):
    wv.append(list(map(int, input().split())))
wv.sort(key=lambda x:(x[0], -x[1]))

wbase = wv[0][0]
for w, v in wv:
    if(w == wbase):
        w0.append(v)
    elif(w == wbase+1):
        w1.append(v)
    elif(w == wbase+2):
        w2.append(v)
    else:
        w3.append(v)
        
sw0, sw1, sw2, sw3 = [0], [0], [0], [0]
s = 0
for v in w0:
    s += v
    sw0.append(s)
s = 0
for v in w1:
    s += v
    sw1.append(s)
s = 0
for v in w2:
    s += v
    sw2.append(s)
s = 0
for v in w3:
    s += v
    sw3.append(s)
    
value = 0
ans = 0
for i in range(len(sw0)):
    if(wbase*i > W):
        break
    for j in range(len(sw1)):
        if(wbase*i+(wbase+1)*j > W):
            break
        for k in range(len(sw2)):
            if(wbase*i+(wbase+1)*j+(wbase+2)*k > W):
                break
            for l in range(len(sw3)):
                if(wbase*i+(wbase+1)*j+(wbase+2)*k+(wbase+3)*l > W):
                    break
                value = sw0[i]+sw1[j]+sw2[k]+sw3[l]
                ans = max(ans, value)        
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = list(map(int, input().split()))
w1 = wv[0]

wvs = [[] for i in range(4)]
wvs[0].append(wv[1])

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

s = [0] * 4
for i in range(4):
  wvs[i] = sorted(wvs[i], reverse = True)
  s[i] = len(wvs[i])
  if s[i] > 1:
    for j in range(1, s[i]):
      wvs[i][j] += wvs[i][j - 1]
  wvs[i].insert(0, 0)
#print(wvs)

ans = 0
for i in range(s[0] + 1):
  for j in range(s[1] + 1):
    for k in range(s[2] + 1):
      for l in range(s[3] + 1):
        weight = w1 * (i + j + k + l) + (j + 2 * k + 3 * l)
        if weight <= W:
          value = wvs[0][i] + wvs[1][j] + wvs[2][k] + wvs[3][l]
          ans = max(ans, value)
          
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate, product
def solve():
    N,W = map(int,input().split())
    value = [list() for _ in range(4)]
    w1 = None
    for i in range(N):
        w,v = map(int,input().split())
        if i == 0:
            w1 = w
        value[w-w1].append(v)
    
    acc = []
    for i in range(4):
        value[i].sort(reverse=True)
        acc.append(list(accumulate(value[i])))
    
    comb = []
    for i_0 in range(len(acc[0]) + 1):
        for i_1 in range(len(acc[1]) + 1):
            for i_2 in range(len(acc[2]) + 1):
                for i_3 in range(len(acc[3]) + 1):
                    comb.append((i_0,i_1,i_2,i_3))
    ans = 0
    for c in comb:
        if isOver(c, acc):
            continue
        sum_w = c[0] * w1 + c[1] * (w1+1) + c[2] * (w1+2) + c[3] * (w1+3)
        if sum_w > W:
            continue
        res = 0
        for i in range(4):
            if c[i] == 0:
                continue
            res += acc[i][c[i]-1]
        
        ans = max(ans,res)
    
    print(ans)

def isOver(c, acc):
    res = False
    for i in range(4):
        if len(acc[i]) < c[i]:
            res = True
    
    return res
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
a,b=map(int,input().split())
w0=[b]
w1=[]
w2=[]
w3=[]
for i in range(N-1):
    w,v=map(int,input().split())
    if w-a==0:
        w0.append(v)
    elif w-a==1:
        w1.append(v)
    elif w-a==2:
        w2.append(v)
    else:
        w3.append(v)
w0=sorted(w0,reverse=True)
w1=sorted(w1,reverse=True)
w2=sorted(w2,reverse=True)
w3=sorted(w3,reverse=True)
ans=0
for i in range(max(len(w0)+1,1)):
    for j in range(max(len(w1)+1,1)):
        for k in range(max(len(w2)+1,1)):
            for l in range(max(len(w3)+1,1)):
                if a*i+(a+1)*j+(a+2)*k+(a+3)*l<=W:
                    lst=w0[:i]+w1[:j]+w2[:k]+w3[:l]
                    ans=max(sum(lst),ans)
print(ans)

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w1,v=map(int,input().split())
if w1>W:
    print(0)
    exit()
lst=[[-1]*(3*N-2) for _ in range(N)]
lst[0][0]=v
for i in range(N-1):
    w,v=map(int,input().split())
    for j in range(N-1,-1,-1):
        for k in range(3*N-2):
            if lst[j][k]!=-1:
                if (j+1)*w1+k+w<=W:
                    lst[j+1][k+w-w1]=max(lst[j][k]+v,lst[j+1][k+w-w1])
    lst[0][w-w1]=max(v,lst[0][w-w1])

lst=[i for j in lst for i in j]
print(max(lst))

Submission status: Accepted

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

W1,V1 = map(int, input().split())

P = {W1:[V1], W1+1:[], W1+2:[], W1+3:[]}

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

PS={}
for k,v in P.items():
  v.sort(reverse=True)
  S = [0] * (len(v)+1)
  for i in range(len(v)):
    S[i+1] = S[i] + v[i]
  PS[k] = S
  
#print(P)
#print(PS)
A,B,C,D = len(PS[W1]), len(PS[W1+1]), len(PS[W1+2]), len(PS[W1+3])
ans = 0
for a in range(A):
  for b in range(B):
    for c in range(C):
      for d in range(D):
        if a*W1 + b*(W1+1) + c*(W1+2) + d*(W1+3) > W:
          continue
        ans = max(ans, PS[W1][a] + PS[W1+1][b] + PS[W1+2][c] + PS[W1+3][d])
        
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import accumulate

    n, k = map(int, readline().split())
    item = [[] for _ in range(4)]
    cnt = [0] * 4

    w, v = map(int, readline().split())
    first = w
    item[0].append(v)
    cnt[0] += 1

    for i in range(n - 1):
        w, v = map(int, readline().split())
        item[w - first].append(v)
        cnt[w - first] += 1

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

    acc = [[0] + list(accumulate(item[i])) for i in range(4)]

    ans = 0
    for p in range(cnt[0] + 1):
        for q in range(cnt[1] + 1):
            for r in range(cnt[2] + 1):
                for s in range(cnt[3] + 1):
                    weight = (p + q + r + s) * first + q + 2 * r + 3 * s
                    if weight > k:
                        break
                    value = acc[0][p] + acc[1][q] + acc[2][r] + acc[3][s]
                    ans = max(ans, value)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

v1=[]
v2=[]
v3=[]
v4=[]

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

for _ in range(n-1):
    w,v=map(int,input().split())
    if w1==w:
        v1.append(v)
    elif w1+1==w:
        v2.append(v)
    elif w1+2==w:
        v3.append(v)
    elif w1+3==w:
        v4.append(v)

v1.sort(reverse=True)
v2.sort(reverse=True)
v3.sort(reverse=True)
v4.sort(reverse=True)

v=[v1,v2,v3,v4]

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

for i,item in enumerate(v):
    tmp=[0]
    tmpv=0
    for j in item:
        tmpv+=j
        tmp.append(tmpv)
    sumv[i]=tmp

ans=0
#print(sumv)
for num1 in range(len(sumv[0])):
    for num2 in range(len(sumv[1])):
        for num3 in range(len(sumv[2])):
            for num4 in range(len(sumv[3])):

                tmpans=0
                tmpwait=0
                if sumv[0][num1]!=0:
                    tmpans+=sumv[0][num1]
                    tmpwait+=(num1)*(w1)
                if sumv[1][num2]!=0:
                    tmpans+=sumv[1][num2]
                    tmpwait+=(num2)*(w1+1)
                if sumv[2][num3]!=0:
                    tmpans+=sumv[2][num3]
                    tmpwait+=(num3)*(w1+2)
                if sumv[3][num4]!=0:
                    tmpans+=sumv[3][num4]
                    tmpwait+=(num4)*(w1+3)

                if tmpwait<=W:
                    ans=max(ans,tmpans)

print(ans)

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
kind=[[] for _ in range(4)]
for i in range(n):
    w_,v=map(int,input().split())
    if i==0:
        stan=w_
    kind[w_-stan].append(v)
for i in range(4):
    kind[i].sort(reverse=True)
    if len(kind[i])>=2:
        for j in range(len(kind[i])-1):
            kind[i][j+1]+=kind[i][j]
    kind[i]=[0]+kind[i]
ans=0
for i in range(len(kind[0])):
    for j in range(len(kind[1])):
        for k in range(len(kind[2])):
            for l in range(len(kind[3])):
                if stan*i+(stan+1)*j+(stan+2)*k+(stan+3)*l<=w:
                    ans=max(ans,kind[0][i]+kind[1][j]+kind[2][k]+kind[3][l])
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,w=MI()
lis=[LI() for i in range(n)]
u=lis[0][0]
vals=[[] for i in range(4)]
for i in range(n):
    if lis[i][0]==u:
        vals[0].append(lis[i][1])
    elif lis[i][0]==u+1:
        vals[1].append(lis[i][1])
    elif lis[i][0]==u+2:
        vals[2].append(lis[i][1])
    else:
        vals[3].append(lis[i][1])
#print(vals)
for i in range(4):
    vals[i].sort(reverse=True)
    vals[i]=list(accumulate(vals[i]))
    vals[i]=[0]+vals[i]
mx=0
#print(vals)
for i in range(len(vals[0])):
    for j in range(len(vals[1])):
        for k in range(len(vals[2])):
            for l in range(len(vals[3])):
                if u*i+(u+1)*j+(u+2)*k+(u+3)*l>w:
                    continue
                V=vals[0][i]+vals[1][j]+vals[2][k]+vals[3][l]
                if V>mx:
                    mx=V
print(mx)