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: Wrong Answer

Solution code:
n,w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [[] for _ in range(4)]
for i,j in a:
    b[i-a[0][0]].append(j)
#print(b)
if (a[0][0]>=500):
    x = w//a[0][0]
    y = w%a[0][0]
    z = b[0]+b[1]+b[2]+b[3]
    z.sort()
    z.reverse()
    if (y>3*n):
        print(sum(z[:x]))
    else:
        dp = [[0]*(y+1) for _ in range(n+1)]
        for i in range(1,n+1):
            for j in range(0,y+1):
                if (j<(a[i-1][0]-a[0][0])):
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-a[i-1][0]+a[0][0]]+a[i-1][1])
        print(max(sum(z[:x-1]),dp[n][y]))
else:
    dp = [[0]*((a[0][0]+3)*n) for _ in range(n+1)]
    for i in range(1,n+1):
        #print(dp[i-1])
        for j in range(0,(a[0][0]+3)*n):
            if (j<a[i-1][0]):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i-1][0]]+a[i-1][1])
    #print(dp[n])
    if (w<(a[0][0]+3)*n):
        print(dp[n][w])
    else:
        print(dp[n][-1])

Submission status: Wrong Answer

Solution code:
n,w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [[] for _ in range(4)]
for i,j in a:
    b[i-a[0][0]].append(j)
#print(b)
if (a[0][0]>=500):
    x = w//a[0][0]
    y = w%a[0][0]
    z = b[0]+b[1]+b[2]+b[3]
    z.sort()
    z.reverse()
    if (y>3*n):
        print(sum(z[:x]))
    else:
        dp = [[0]*(y+1) for _ in range(n+1)]
        for i in range(1,n+1):
            for j in range(a[i-1][0],y+1):
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-a[i-1][0]]+a[i-1][1])
        print(max(sum(z[:x-1]),dp[n][y]))
else:
    dp = [[0]*((a[0][0]+3)*n) for _ in range(n+1)]
    for i in range(1,n+1):
        #print(dp[i-1])
        for j in range(0,(a[0][0]+3)*n):
            if (j<a[i-1][0]):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i-1][0]]+a[i-1][1])
    #print(dp[n])
    print(dp[n][w])

Submission status: Wrong Answer

Solution code:
n,w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [[] for _ in range(4)]
for i,j in a:
    b[i-a[0][0]].append(j)
#print(b)
if (a[0][0]>=500):
    x = w//a[0][0]
    y = w%a[0][0]
    z = b[0]+b[1]+b[2]+b[3]
    z.sort()
    z.reverse()
    if (y>3*n):
        print(sum(z[:x]))
    else:
        dp = [[0]*(y+1) for _ in range(n+1)]
        for i in range(1,n+1):
            for j in range(a[i-1][0],y+1):
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-a[i-1][0]]+a[i-1][1])
        print(max(sum(z[:x-1]),dp[n][y]))
else:
    dp = [[0]*((a[0][0]+3)*n) for _ in range(n+1)]
    for i in range(1,n+1):
        #print(dp[i-1])
        for j in range(0,(a[0][0]+3)*n):
            if (j<a[i-1][0]):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i-1][0]]+a[i-1][1])
    #print(dp[n])
    print(max(dp[n][:w+1]))

Submission status: Wrong Answer

Solution code:
def main():
    n, w = map(int, input().split())
    lk = {}
    w1, v1 = map(int, input().split())
    values = [[] for _ in range(4)]
    values[0].append(v1)
    for _ in range(n - 1):
        wi, vi = map(int, input().split())
        values[wi - w1].append(vi)
    prefix = [[0] for _ in range(4)]
    for i in range(4):
        for j in range(len(values[i])):
            prefix[i].append(prefix[i][-1] + values[i][j])
    max_ans = 0
    tot_val = [0] * 4
    tot_weights = [0] * 4
    for i in range(min(len(values[0]), w // w1) + 1):
        tot_val[0] = prefix[0][i]
        tot_weights[0] = w1 * i
        for j in range(min(len(values[1]), w // (w1 + 1)) + 1):
            tot_val[1] = tot_val[0] + prefix[1][j]
            tot_weights[1] = tot_weights[0] + (w1 + 1) * j
            if tot_weights[1] > w:
                break
            for k in range(min(len(values[2]), w // (w1 + 2)) + 1):
                tot_val[2] = tot_val[1] + prefix[2][k]
                tot_weights[2] = tot_weights[1] + k * (w1 + 2)
                if tot_weights[2] > w:
                    break
                diff = w - tot_weights[2]
                min_select = min(diff // (w1 + 3), len(values[3]))
                tot_val[3] = tot_val[2] + prefix[3][min_select]
                tot_weights[3] = tot_weights[2] + min_select * (w1 + 3)
                max_ans = max(max_ans, tot_val[3])
    print(max_ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,w = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp=[[ 0 for i in range(w+1)] for j in range(n+1)]

if ab[0][0] >w:
    print(0)
    exit()

for i in range(n):
    for j in range(ab[0][0],min((i+1)*(ab[0][0]+4),w+1)):
        if j < ab[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max((dp[i][j-ab[i][0]]+ab[i][1]),dp[i][j])
print(dp[n][w])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    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())
    if w[0]>3*N:
        w0=w[0]
        W=min(W//w0*(3*N+1)+W%w0,(3*N+4)*N)
        for i in range(N):
            w[i]-=w0
            w[i]+=3*N+1
    dp=[[0]*(W+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])
            if j-w[i]>=0:
                dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
    print(dp[-1][-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
wv = [[int(i) for i in input().split()] for j in range(n)]

wv.sort(key=lambda x:(x[0],-x[1]))
#print(wv)
#exit()
#wv.sort()
min_v = wv[0][0]
cnt = 0
num = [0]*4

for i in range(n):
    num[wv[i][0] - min_v] +=1
        
#dp = [[[0 for i in range(n)] for j in range(n)] for k in range(n)]

#print(wv)

t_num3 = [0]
tmp = 0
for i in range(num[3]):
    tmp += wv[n-num[3]+i][1]
    t_num3.append(tmp)

#print(t_num3)
#exit()

t_ans = 0
t_num0 = 0
ans = 0


for i in range(num[0]+1):
    if i != 0:
        t_num0 += wv[i-1][1]
    #print(t_ans,i)
    t_num1 = 0
    for j in range(num[1]+1):
        if j != 0:
            t_num1 += wv[num[0]+j-1][1]
        t_num2 = 0
        for k in range(num[2]+1):
            if k != 0:
                t_num2 += wv[num[0]+num[1]+k-1][1]
            ima_w = min_v*(i+j+k) + 1*j+2*k
            idx = (w - ima_w)//(min_v+3)
            if ima_w > w:
                break
            else:
                t_ans = t_num0+t_num1+t_num2 + t_num3[min(idx,num[3])]
        #print(t_ans)
        ans = max(t_ans,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
wv = [[int(i) for i in input().split()] for j in range(n)]

wv.sort(key=lambda x:(x[0],-x[1]))
#print(wv)
#exit()
#wv.sort()
min_v = wv[0][0]
cnt = 0
num = [0]*4

for i in range(n):
    num[wv[i][0] - wv[0][0]] +=1
        
#dp = [[[0 for i in range(n)] for j in range(n)] for k in range(n)]

#print(wv)

t_num3 = [0]
tmp = 0
for i in range(num[3]):
    tmp += wv[n-num[3]+i][1]
    t_num3.append(tmp)

t_ans = 0
t_num0 = 0
ans = 0


for i in range(num[0]+1):
    if i != 0:
        t_num0 += wv[i-1][1]
    #print(t_ans,i)
    t_num1 = 0
    for j in range(num[1]+1):
        if j != 0:
            t_num1 += wv[num[0]+j-1][1]
        t_num2 = 0
        for k in range(num[2]+1):
            if k != 0:
                t_num2 += wv[num[0]+num[1]+k-1][1]
            ima_w = min_v*(i+j+k) + 1*j+2*k
            idx = (w - ima_w)//(min_v+3)
            if ima_w > w:
                continue
            else:
                t_ans = t_num0+t_num1+t_num2 + t_num3[min(idx,num[3])]
        #print(t_ans)
        ans = max(t_ans,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
wv = [[int(i) for i in input().split()] for j in range(n)]

wv.sort(key=lambda x:(x[0],-x[1]))
#print(wv)
#exit()
#wv.sort()
min_v = wv[0][0]
cnt = 0
num = [0]*4

for i in range(n):
    num[wv[i][0] - wv[0][0]] +=1
        
#dp = [[[0 for i in range(n)] for j in range(n)] for k in range(n)]

#print(wv)

t_num3 = [0]
tmp = 0
for i in range(num[3]):
    tmp += wv[n-num[3]-1+i][1]
    t_num3.append(tmp)

t_ans = 0
t_num0 = 0
ans = 0

for i in range(num[0]+1):
    if i != 0:
        t_num0 += wv[i-1][1]
    #print(t_ans,i)
    t_num1 = 0
    for j in range(num[1]+1):
        if j != 0:
            t_num1 += wv[num[0]+j-1][1]
        t_num2 = 0
        for k in range(num[2]+1):
            if k != 0:
                t_num2 += wv[num[0]+num[1]+k-1][1]
            ima_w = min_v*(i+j+k) + 1*j+2*k
            idx = (w - ima_w)//(min_v+3)
            if ima_w > w:
                continue
            else:
                t_ans = t_num0+t_num1+t_num2 + t_num3[min(idx,num[3])]
        #print(t_ans)
        ans = max(t_ans,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
wv = [[int(i) for i in input().split()] for j in range(n)]

wv.sort(key=lambda x:(x[0],-x[1]))
#print(wv)
#exit()
#wv.sort()
min_v = wv[0][0]
cnt = 0
num = [0]*4

for i in range(n):
    num[wv[i][0] - wv[0][0]] +=1
        
#dp = [[[0 for i in range(n)] for j in range(n)] for k in range(n)]

#print(wv)

t_num3 = [0]
tmp = 0
for i in range(num[3]):
    tmp += wv[n-num[3]-1+i][1]
    t_num3.append(tmp)

t_ans = 0
t_num0 = 0
ans = 0

for i in range(num[0]+1):
    if i != 0:
        t_num0 += wv[i-1][1]
    #print(t_ans,i)
    t_num1 = 0
    for j in range(num[1]+1):
        if j != 0:
            t_num1 += wv[num[0]+j-1][1]
        t_num2 = 0
        for k in range(num[2]+1):
            if k != 0:
                t_num2 += wv[num[0]+num[1]+k-1][1]
            ima_w = min_v*(i+j+k) + 1*j+2*k
            idx = (w - ima_w)//(min_v+3)
            if ima_w > w:
                continue
            else:
                t_ans = t_num0+t_num1+t_num2 + t_num3[min(idx,num[3]-1)]
        #print(t_ans)
        ans = max(t_ans,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
wv = [[int(i) for i in input().split()] for j in range(n)]

wv.sort(key=lambda x:(x[0],-x[1]))
#print(wv)
#exit()
#wv.sort()
min_v = wv[0][0]
cnt = 0
num = [0]*4

for i in range(n):
    num[wv[i][0] - wv[0][0]] +=1
        
#dp = [[[0 for i in range(n)] for j in range(n)] for k in range(n)]

#print(wv)

t_num3 = []
tmp = 0
for i in range(num[3]):
    tmp += wv[n-num[3]-1+i][1]
    t_num3.append(tmp)

t_ans = 0
t_num0 = 0
ans = 0

for i in range(num[0]+1):
    if i != 0:
        t_num0 += wv[i-1][1]
    #print(t_ans,i)
    t_num1 = 0
    for j in range(num[1]+1):
        if j != 0:
            t_num1 += wv[num[0]+j-1][1]
        t_num2 = 0
        for k in range(num[2]+1):
            if k != 0:
                t_num2 += wv[num[0]+num[1]+k-1][1]
            ima_w = min_v*(i+j+k) + 1*j+2*k
            idx = (w - ima_w)//(min_v+3) - 1
            if ima_w > w:
                continue
            elif num[3] == 0 or idx < 0:
                t_ans = t_num0+t_num1+t_num2
            else:
                t_ans = t_num0+t_num1+t_num2 + t_num3[min(idx,num[3]-1)]
        #print(t_ans)
        ans = max(t_ans,ans)

print(ans)

Submission status: Wrong Answer

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

# dp = [[float('inf') for _ in range(10**7+1)] for _ in range(n+1)]
# dp[0] = [0 for _ in range(10**7+1)]

dp_dict = {0: {0:0}} # w,v

'''
for i,pack in enumerate(pack_list):
    for value,weight in enumerate(dp[i]):
        dp[i+1][value] = min(dp[i][value],dp[i+1][value])
        dp[i+1][value+pack[1]] = min(dp[i+1][value+pack[1]],dp[i][value]+pack[0])

for i,num in enumerate(dp[-1][::-1]):
    if num <= w:
        print(10**7-i)'''

for i,pack in enumerate(pack_list):
    i += 1
    if i not in dp_dict:
        dp_dict[i] = {}
    for weight,v in dp_dict[i-1].items():
        if weight not in dp_dict[i]:
            dp_dict[i][weight] = v
        else:
            dp_dict[i][weight] = max(dp_dict[i][weight],v)
        if weight+pack[0] <= weight:
            if weight+pack[0] not in dp_dict[i]:
                dp_dict[i][weight+pack[0]] = v+pack[1]
            else:
                dp_dict[i][weight+pack[0]] = max(dp_dict[i][weight+pack[0]],v+pack[1])

target = dp_dict[n]
max_num = 0

for k,v in target.items():
    if k <= w:
        max_num = max(max_num,v)

print(max_num)

Submission status: Wrong Answer

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

w0 = X[0][0]
ctr = [[] for _ in range(4)]
for w, v in X:
    ctr[w - w0].append(v)

for n in range(4):
    values = sorted(ctr[n])
    s = [0] * (len(values) + 1)
    for i in range(len(values)):
        s[i + 1] = s[i] + values[i]
    ctr[n] = s

ans = 0
for i in range(len(ctr[0])):
    for j in range(len(ctr[1])):
        for k in range(len(ctr[2])):
            for l in range(len(ctr[3])):
                tmp = ctr[0][i] + ctr[1][j] + ctr[2][k] + ctr[3][l]
                w = w0 * i + (w0 + 1) * j + (w0 + 2) * k + (w0 + 3) * l
                if w <= W:
                    ans = max(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N,W=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
AB=sorted(AB, key=lambda x:x[1],reverse=True)  #価値降順
AB=sorted(AB)  #重さ昇順
w0,w1,w2,w3=[0],[0],[0],[0]
w=AB[0][0]
#print(AB)
j=0
while j<N and AB[j][0]==w:
    w0.append(AB[j][1])
    j+=1
if j<N: w=AB[j][0]
while j<N and AB[j][0]==w:
    w1.append(AB[j][1])
    j+=1
if j<N: w=AB[j][0]
while j<N and AB[j][0]==w:
    w2.append(AB[j][1])
    j+=1
if j<N: w=AB[j][0]
while j<N and AB[j][0]==w:
    w3.append(AB[j][1])
    j+=1
#print(w0,w1,w2,w3)
w=AB[0][0]
w0=list(accumulate(w0))
w1=list(accumulate(w1))
w2=list(accumulate(w2))
w3=list(accumulate(w3))

check=[]
ans=0
for a in range(len(w0)):
    for b in range(len(w1)):
        for c in range(len(w2)):
            for d in range(len(w3)):
                check.append((a,b,c,d))
                wei=w*a+(w+1)*b+(w+2)*c+(w+3)*d
                val=w0[a]+w1[b]+w2[c]+w3[d]
                if wei<=W:
                    ans=max(val,ans)

#print(check)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product
from collections import  defaultdict as dd
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
wi = wv[0][0]
vi = wv[0][1]
dic = dd(list)
dic_cumsum = dd(list)
for w,v in wv:
    dic[w].append(v)

for k,v in dic.items():
    dic_cumsum[k] = sorted(dic_cumsum[k], reverse=True)
    dic_cumsum[k] = [0] + list(np.zeros((N + 1), dtype=np.int64))
    dic_cumsum[k][1:] = list(np.cumsum(v, dtype=np.int64))
for i in range(1,4):
    if wi+i not in dic_cumsum.keys():
        dic_cumsum[wi+i] = [0]
        
n = [len(dic_cumsum[wi]), len(dic_cumsum[wi+1]), len(dic_cumsum[wi+2]), len(dic_cumsum[wi+3])]
m = [list(range(val)) for val in n]
res = 0

for ls in product(m[0], m[1], m[2]):
    if sum(ls)*wi > W:
        continue
    tmp_value = 0
    tmp_weight = 0
    for i,k in enumerate(ls):
        tmp_value += dic_cumsum[wi + i][k]
        tmp_weight += k*(wi+i)
    if tmp_weight > W:
        continue
    # wi, wi+1, wi+2の個数が決まっているので、wi+3を何個取れるかはO(1)で求められる
    max_m3 = (W - tmp_weight) // (wi+3)
    m3 = min(max_m3, n[3]-1)
    tmp_value += dic_cumsum[wi+3][m3]
    if tmp_value > res:
        res = tmp_value
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product
from collections import  defaultdict as dd
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
wi = wv[0][0]
vi = wv[0][1]
dic = dd(list)
dic_cumsum = dd(list)
for w,v in wv:
    dic[w].append(v)

for k,v in dic.items():
    dic_cumsum[k] = [0] + list(np.zeros((N + 1), dtype=np.int64))
    dic_cumsum[k][1:] = list(np.cumsum(v, dtype=np.int64))
for i in range(1,4):
    if wi+i not in dic_cumsum.keys():
        dic_cumsum[wi+i] = [0]
        
n = [len(dic_cumsum[wi]), len(dic_cumsum[wi+1]), len(dic_cumsum[wi+2]), len(dic_cumsum[wi+3])]
m = [list(range(val)) for val in n]
res = 0

for ls in product(m[0], m[1], m[2], m[3]):
    tmp_value = 0
    tmp_weight = 0
    for i in range(4):
        tmp_value += dic_cumsum[wi + i][ls[i]]
        tmp_weight += ls[i]*(wi+i)
    if tmp_weight > W:
        continue
    if tmp_value > res:
        res = tmp_value
print(res)

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(n)]
t = [[] for _ in range(4)]
for u in s:
    t[u[0] - s[0][0]].append(u[1])
l1, l2, l3, l4 = len(t[0]) + 1, len(t[1]) + 1, len(t[2]) + 1, len(t[3]) + 1
a, b, = [0] * l1, [0] * l2
c, d, = [0] * l3, [0] * l4
for i in range(1, l1):
    a[i] = t[0][i - 1] + a[i - 1]
for i in range(1, l2):
    b[i] = t[1][i - 1] + b[i - 1]
for i in range(1, l3):
    c[i] = t[2][i - 1] + c[i - 1]
for i in range(1, l4):
    d[i] = t[3][i - 1] + d[i - 1]
ans = 0
for i in range(l1):
    for j in range(l2):
        for k in range(l3):
            for l in range(l4):
                if s[0][0] * (i + j + k + l) + (j + 2 * k + 3 * l) <= w:
                    ans = max(ans, a[i] + b[j] + c[k] + d[l])
print(ans)

Submission status: Wrong Answer

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

for k in wv.keys():
    wv[k].sort(reverse=True)

kw = list(wv.keys())
kw.sort()
l = [len(wv[k]) for k in kw]
l = l + (3 - len(l)) * [0]
# print(l)

ans = 0
for i in range(l[0]+1):
    for j in range(l[1]+1):
        for k in range(l[2]+1):
            tot_w = kw[0] * i
            if 2 <= len(kw):
                tot_w += kw[1] * j
            if 3 <= len(kw):
                tot_w += kw[2] * k
            if W < tot_w:
                break
            tmp = sum(wv[kw[0]][:i])
            if 2 <= len(kw):
                tmp += sum(wv[kw[1]][:j])
            if 3 <= len(kw):
                tmp += sum(wv[kw[2]][:k])
            ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

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

for k in wv.keys():
    wv[k].sort(reverse=True)

kw = list(wv.keys())
kw.sort()
l = [len(wv[k]) for k in wv.keys()]
l = l + (3 - len(l)) * [0]
# print(l)

ans = 0
for i in range(l[0]+1):
    for j in range(l[1]+1):
        for k in range(l[2]+1):
            tot_w = kw[0] * i
            if 2 <= len(kw):
                tot_w += kw[1] * j
            if 3 <= len(kw):
                tot_w += kw[2] * k
            if W < tot_w:
                break
            tmp = sum(wv[kw[0]][:i])
            if 2 <= len(kw):
                tmp += sum(wv[kw[1]][:j])
            if 3 <= len(kw):
                tmp += sum(wv[kw[2]][:k])
            ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

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

for k in wv.keys():
    wv[k].sort(reverse=True)

kw = list(wv.keys())
kw.sort()
l = [len(wv[k]) for k in wv.keys()]
l = l + (3 - len(l)) * [0]
# print(l)

ans = 0
for i in range(l[0]+1):
    for j in range(l[1]+1):
        for k in range(l[2]+1):
            tot_w = kw[0] * i
            if 2 <= len(kw):
                tot_w += kw[1] * j
            if 3 <= len(kw):
                tot_w += kw[2] * k
            if W < tot_w:
                break
            tmp = wv[kw[0]][:i]
            if 2 <= len(kw):
                tmp += wv[kw[1]][:j]
            if 3 <= len(kw):
                tmp += wv[kw[2]][:k]
            tmp = sum(tmp)
            ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
weights, values = zip(*[tuple(map(int, input().split()))for _ in range(n)])
min_w = min(weights)-1
weights = [weight-min_w for weight in weights]
W_MAX = 4*200
dp = [[0]*(W_MAX+1) for _ in range(n+1)]
for i in range(1, n+1):
    for k in reversed(range(1, n+1)):
        for j in range(1, W_MAX+1):
            if j-weights[i-1] < 0:
                continue
            dp[k][j] = max(dp[k][j], dp[k-1][j-weights[i-1]]+values[i-1])

ans = 0
for k in range(n+1):
    w_max = w-k*min_w
    if w_max < 0 or W_MAX < w_max:
        continue
    ans = max(ans, dp[k][w_max])
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    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
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,W = map(int, input().split())
    w,v = [], []
    for i in range(n):
        a,b = map(int, input().split())
        if i == 0:
            w.append(a)
        else:
            w.append(a - w[0])
        v.append(b)
    #w1の重さ
    base = w[0]
    w[0] = 0
    w0, w1, w2, w3 = [], [], [], []
    for i in range(n):
        if w[i] == 0:
            w0.append(v[i])
        if w[i] == 1:
            w1.append(v[i])
        if w[i] == 2:
            w2.append(v[i])
        if w[i] == 3:
            w3.append(v[i])
    w0.sort()
    w1.sort()
    w2.sort()
    w3.sort()
    w0 = [0] + w0
    w1 = [0] + w1
    w2 = [0] + w2
    w3 = [0] + w3
    w0 = list(accumulate(w0))
    w1 = list(accumulate(w1))
    w2 = list(accumulate(w2))
    w3 = list(accumulate(w3))

    res = 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 base*(i+j+k+l) + j + k*2 + l*3 <= W:
                        res = max(res, w0[i]+w1[j]+w2[k]+w3[l])
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
L = 100000
dp = [[1000000001 for _ in range(L+1)] for _ in range(N+1)]
W, V = [], []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
dp[0][0] = 0
for i in range(N):
    for j in range(L+1):
        if j - V[i] >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j-V[i]] + W[i])
        else:
            dp[i+1][j] = dp[i][j]
for i, d in enumerate(dp[N]):
    if d <= M:
        maxv = i
print(maxv)

Submission status: Wrong Answer

Solution code:
#060_D
n, W = map(int, input().split())
w1, w2, w3, w4 = [], [], [], []
w, v = map(int, input().split())
w1.append(v)
for _ in range(n-1):
    a, b = map(int, input().split())
    if a == w: w1.append(b)
    if a == w+1: w2.append(b)
    if a == w+2: w3.append(b)
    if a == w+3: w4.append(b)
    
for w_ in [w1, w2, w3, w4]:
    w_.sort(reverse= True)
    
ans = 0
for i in range(0, len(w1)+1):
    for j in range(0, len(w2)+1):
        for k in range(0, len(w3)+1):
            res = i * w + j * (w+1) + k * (w+2)
            if res > W:
                continue
            tmp = sum(w1[:i])+sum(w2[:j])+sum(w3[:k])+sum(w4[:res//(w+3)])
            ans = max(tmp, ans)
            
print(ans)

Submission status: Wrong Answer

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

N, W = [int(x) for x in input().split()]
wv = []
for _ in range(N):
    wv.append([int(x) for x in input().split()])
w1 = wv[0][0]
dp = [[[0, 0] for _ in range(4 * N + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    w, v = wv[i - 1]
    w -= (w1 - 1)
    for j in range(4 * N + 1):
        if j - w >= 0:
            if dp[i - 1][j - w][0] + v > dp[i - 1][j][0]:
                dp[i][j] = [dp[i - 1][j - w][0] + v, dp[i - 1][j - w][1] + 1]
            elif dp[i - 1][j - w][0] + v == dp[i - 1][j][0]:
                dp[i][j] = [dp[i - 1][j - w][0] + v, min(dp[i - 1][j - w][1] + 1, dp[i - 1][j][1])]
            else:
                dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = dp[i - 1][j]

ans = 0

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

print(ans)

Submission status: Wrong Answer

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

N, W = [int(x) for x in input().split()]
wv = []
for _ in range(N):
    wv.append([int(x) for x in input().split()])
w1 = wv[0][0]
dp = [[[0, 0] for _ in range(4 * N + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    w, v = wv[i - 1]
    w -= (w1 - 1)
    for j in range(4 * N + 1):
        if j - w >= 0:
            if dp[i - 1][j - w][0] + v > dp[i - 1][j][0]:
                dp[i][j] = [dp[i - 1][j - w][0] + v, dp[i - 1][j - w][1] + 1]
            else:
                dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = dp[i - 1][j]

ans = 0

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

print(ans)

Submission status: Wrong Answer

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

value_table = [[] for i in range(4)]
for i in range(N):
    w, v = map(int,input().split())
    if i == 0:
        w1 = w
    value_table[w-w1] += [v]

[value_table[i].sort() for i in range(4)]

ans = 0
value_table_ruiseki = [[0] for i in range(4)]
for i in range(4):
    for v in value_table[i]:
        value_table_ruiseki[i] += [value_table_ruiseki[i][-1] + v]

ans = 0
for i, iv in enumerate(value_table_ruiseki[0]):
    for j, jv in enumerate(value_table_ruiseki[1]):
        for k, kv in enumerate(value_table_ruiseki[2]):
            for ell, ellv in enumerate(value_table_ruiseki[3]):
                weight = i*w1 + j*(w1+1) + k*(w1+2) + ell*(w1+3)
                value = iv + jv + kv + ellv
                if weight <=W:
                    ans = max(ans, value)

print(ans)

Submission status: Wrong Answer

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 w, v in wv:
    items = tuple(dp.items())
    for k, val in items:
        if k + w <= W:
            dp[k + w] = max(dp[k + w], dp[k] + v)

ans = max(dp.values())
print(ans)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

import bisect

def main():
    mod=10**9+7
    N,W=MI()
    w=[0]*N
    v=[0]*N
    for i in range(N):
        w[i],v[i]=MI()
    w1=w[0]
    for i in range(N):
        w[i]-=w1
        
    a=set([0])
    for i in range(N):
        for j in range(4*(i+1)):
            ww=w1*i+j
            if ww>W:
                break
            a.add(w1*i+j)
    a=list(a)
    M=len(a)
    
    
    #dp[i][j]はiまでの商品で,重さa[j]のときの価値の最大
    dp=[[-1]*(M) for _ in range(N+1)]
    for i in range(N):
        dp[i][0]=0
    ans=0
    
    for i in range(N):
        for j in range(M):
            if dp[i][j]!=-1:
                dp[i+1][j]=max(dp[i+1][j],dp[i][j])
                ww=a[j]+w1+w[i]
                jj=bisect.bisect_left(a,ww)
                if jj<M:
                    dp[i+1][jj]=max(dp[i+1][jj],dp[i][j]+v[i])
                    ans=max(ans,dp[i+1][jj])
                    
    print(ans)
                    
    
            

main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

import bisect

def main():
    mod=10**9+7
    N,W=MI()
    w=[0]*N
    v=[0]*N
    for i in range(N):
        w[i],v[i]=MI()
    w1=w[0]
    for i in range(N):
        w[i]-=w1
        
    a=set([0])
    for i in range(N):
        for j in range(4*(i)):
            ww=w1*i+j
            if ww>W:
                break
            a.add(w1*i+j)
    a=list(a)
    M=len(a)
    
    
    #dp[i][j]はiまでの商品で,重さa[j]のときの価値の最大
    dp=[[-1]*(M) for _ in range(N+1)]
    for i in range(N):
        dp[i][0]=0
    ans=0
    
    for i in range(N):
        for j in range(M):
            if dp[i][j]!=-1:
                dp[i+1][j]=max(dp[i+1][j],dp[i][j])
                ww=a[j]+w1+w[i]
                jj=bisect.bisect_left(a,ww)
                if jj<M:
                    dp[i+1][jj]=max(dp[i+1][jj],dp[i][j]+v[i])
                    ans=max(ans,dp[i+1][jj])
                    
    print(ans)
                    
    
            

main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N, W = read_values()
    dp = [
        [[0 for _ in range(N * 3 + 100)] for __ in range(N + 10)]
        for ___ in range(N + 10)
    ]
    I = [tuple(read_values()) for _ in range(N)]

    w0 = I[0][0]
    if w0 > W:
        print(0)
        return

    for i, (w1, v) in enumerate(I):
        w = w1 - w0
        for k in range(N):
            for j in range(N * 3 + 5):
                dp[i + 1][k][j] = max(dp[i][k][j], dp[i + 1][k][j])
                if j + w > N * 3 + 10:
                    continue
                dp[i + 1][k + 1][j + w] = max(dp[i][k][j] + v, dp[i + 1][k + 1][j + w])

    res = 0
    for k in range(N + 1):
        r = min(W - k * w0, 3 * N + 10)
        if r < 0:
            continue
        for i in range(r):
            res = max(res, dp[N][k][i])
    print(res)


if __name__ == "__main__":
    main()