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:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LS()
    if a[-1] == b[0] and b[-1] == c[0]:
        print("YES")
    else:
        print("NO")
    return

#B
def B():
    a, b, c = LI()
    for i in range(1, b):
        if a * i % b == c:
            print("YES")
            return
    print("NO")
    return

#C
def C():
    _, T = LI()
    t = LI()
    ans = 0
    now = t[0]
    for i in t[1:]:
        if now + T <= i:
            ans += T
        else:
            ans += i - now
        now = i
    print(ans + T)
    return

#D
def D():
    n, W = LI()
    wv = LIR(n)
    wv.sort()
    dp = [-inf] * (3 * n * n + 1)
    dp[0] = 0
    minw =  wv[0][0]
    if minw < 3 * n:
        for w, v in wv:
            for i in range(3 * n * n, w - 1, -1):
                dp[i] = max(dp[i - w] + v, dp[i])
        print(max(dp[:W + 1]))
    else:
        for w, v in wv:
            w -= minw
            for i in range(n - 1, 0, -1):
                for k in range(3 * n, w - 1, -1):
                    dp[i * 3 * n + k] = max(dp[(i - 1) * 3 * n + k - w] + v, dp[i * 3 * n + k])
        print(max(dp[:W // minw * 3 * n + W % minw + 1]))
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LS()
    if a[-1] == b[0] and b[-1] == c[0]:
        print("YES")
    else:
        print("NO")
    return

#B
def B():
    a, b, c = LI()
    for i in range(1, b):
        if a * i % b == c:
            print("YES")
            return
    print("NO")
    return

#C
def C():
    _, T = LI()
    t = LI()
    ans = 0
    now = t[0]
    for i in t[1:]:
        if now + T <= i:
            ans += T
        else:
            ans += i - now
        now = i
    print(ans + T)
    return

#D
def D():
    n, W = LI()
    wv = LIR(n)
    wv.sort()
    dp = [-inf] * (3 * n * n + 1)
    dp[0] = 0
    minw =  wv[0][0]
    if minw <= 3 * n:
        for w, v in wv:
            for i in range(3 * n * n, w - 1, -1):
                dp[i] = max(dp[i - w] + v, dp[i])
        print(max(dp[:W + 1]))
    else:
        for w, v in wv:
            w -= minw
            for i in range(n - 1, 0, -1):
                for k in range(3 * n, w - 1, -1):
                    dp[i * 3 * n + k] = max(dp[(i - 1) * 3 * n + k - w] + v, dp[i * 3 * n + k])
        print(max(dp[:W // minw * 3 * n + W % minw + 1]))
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
"""
W<=10**9, v<=10**7までなので、普通のDPは間に合わないっぽい
重さが4種類までしかない

"""

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

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

#4種類なければ空の配列が生じる
values = [[],[],[],[]]
min_w = wv[0][0]
for w,v in wv:
    values[w-min_w].append(v)




values[0].sort(reverse=True)
values[1].sort(reverse=True)
values[2].sort(reverse=True)
values[3].sort(reverse=True) 

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

print(ans)

Submission status: Wrong Answer

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

items = [[] for _ in range(4)]
w0, v0 = map(int, input().split())
items[0].append(v0)

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

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

sumItems = [[0 for _ in range(len(items[i]) + 1)] for i in range(4)]

for i in range(4):
    for j, v in enumerate(items[i]):
        sumItems[i][j + 1] = sumItems[i][j] + v

ans = 0
for firstCount in range(len(items[0]) + 1):
    for secondCount in range(len(items[1]) + 1):
        for thirdCount in range(len(items[2]) + 1):
            for forthCount in range(len(items[3]) + 1):
                sumWeight = w0 * firstCount + (w0 + 1) * secondCount + (w0 + 2) * thirdCount + (w0 + 2) * forthCount
                if sumWeight > W:
                    break
                sumV = 0
                for i, count in enumerate([firstCount, secondCount, thirdCount, forthCount]):
                    sumV += sumItems[i][count]
                ans = max(ans, sumV)

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,W = [int(i) for i in readline().split()]
wv = [[int(i) for i in readline().split()] for j in range(n)]

w0 = wv[0][0]

d = [[] for i in range(4)]
for w,v in wv:
    d[w-w0].append(v)

from itertools import accumulate
ac = [None]*4
for i in range(4):
    d[i].sort()
    ac[i] = list(accumulate([0]+d[i]))

#print(d)
#print(ac)

ans = 0
di = len(ac[0])
dj = len(ac[1]) 
dk = len(ac[2]) 
dl = len(ac[3])

ac3 = ac[3]
for i in range(di):
    for j in range(min(n+1-i,dj)):
        for k in range(min(n+1-i-j,dk)):
            Wres = i*w0 + j*(w0+1) + k*(w0+2)
            if Wres > W: continue

            res = ac[0][i] + ac[1][j] + ac[2][k]
            idx = (W-Wres)//(w0+3)
            res += ac3[min(dl-1,idx)]
            if ans < res:
                ans = res

print(ans)

Submission status: Wrong Answer

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

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

if sum([w for w, _ in wv]) - wv[0][0] * N < wv[0][0] :
    wv.sort(key=lambda x: x[1], reverse=True)
    ret = 0
    for w, v in wv :
        if w < W :
            ret += v
            W -= w
    print(ret)
else :
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for i in range(1, N + 1) :
        w, v = wv[i-1]
        for j in range(W+1) :
            if j < w :
                dp[i][j] = dp[i-1][j]
            else :
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - w] + v)
                
    print(dp[N][W])

Submission status: Wrong Answer

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

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

if 3 * N < wv[0][0] :
    wv.sort(key=lambda x: x[1], reverse=True)
    ret = 0
    for w, v in wv :
        if w < W :
            ret += v
            W -= w
    print(ret)

elif sum([w for w, v in wv]) <= W :
    print(sum([v for w, v in wv]))

else :
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for i in range(1, N + 1) :
        w, v = wv[i-1]
        for j in range(W+1) :
            if j < w :
                dp[i][j] = dp[i-1][j]
            else :
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - w] + v)
                
    print(dp[N][W])

Submission status: Wrong Answer

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

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

if 3 * N < wv[0][0] :
    wv.sort(key=lambda x: x[1], reverse=True)
    ret = 0
    for w, v in wv :
        if w < W :
            ret += v
            W -= w
    print(ret)
    
else :
    W = min(W, (wv[0][0] + 3) * N)
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for i in range(1, N + 1) :
        w, v = wv[i-1]
        for j in range(W+1) :
            if j < w :
                dp[i][j] = dp[i-1][j]
            else :
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - w] + v)
                
    print(dp[N][W])

Submission status: Wrong Answer

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

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

if 3 * N < wv[0][0] :
    wv.sort(key=lambda x: x[1], reverse=True)
    ret = 0
    for w, v in wv :
        if w < W :
            ret += v
            W -= w
    print(ret)
    
else :
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for i in range(1, N + 1) :
        w, v = wv[i-1]
        for j in range(W+1) :
            if j < w :
                dp[i][j] = dp[i-1][j]
            else :
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - w] + v)
                
    print(dp[N][W])

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
w1,v1=map(int,input().split())
l1=[v1]
l2=[]
l3=[]
l4=[]
for _ in range(n-1):
    p=[int(i) for i in input().split()]
    if p[0]==w1:
        l1.append(p[1])
    if p[0]==w1+1:
        l2.append(p[1])
    if p[0]==w1+2:
        l3.append(p[1])
    if p[0]==w1+3:
        l4.append(p[1])
l1.sort()
l2.sort()
l3.sort()
l4.sort()
ans=0
for a in range(len(l1)+1):
    for b in range(len(l2)+1):
        for c in range(len(l3)+1):
            for d in range(len(l4)+1):
                if a*w1+b*(w1+1)+c*(w1+2)+d*(w1+3)<=w:
                    ans=max(ans,sum(l1[:a])+sum(l2[:b])+sum(l3[:c])+sum(l4[:d]))
print(ans)

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in [0]*n]
d={0:0}
for w,v in wv:
    temp=dict()
    for k,i in d.items():
        if k+w in d.keys():
            d[k+w]=max(d[k+w],i+v)
        else:
            temp[k+w]=i+v
    d.update(temp)
    s=sorted(d.keys())
    m=-1
    for i in s:
        if d[i]<=m:
            del d[i]
        else:
            m=d[i]
print(max([v for w,v in d.items() if w<=W]+[0]))

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in [0]*n]
d={0:0}
for w,v in wv:
    temp=dict()
    for k,i in d.items():
        if k+w in d.keys():
            d[k+w]=max(d[k+w],i+v)
        else:
            temp[k+w]=i+v
    d.update(temp)

print(max([v for w,v in d.items() if w<=W]+[0]))

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w, v = [None] * N, [None] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
wmin = w[0]
_w = [[], [], [], []]
for i in range(N):
    _w[w[i] - wmin].append(v[i])
for i in range(4):
    _w[i].sort(reverse = 1)
    for j in range(1, len(_w[i])):
        _w[i][j] += _w[i][j-1]
    _w[i].insert(0, 0)
ans = 0
for c0 in range(len(_w[0])):
    for c1 in range(len(_w[1])):
        for c2 in range(len(_w[2])):
            for c3 in range(len(_w[3])):
                if wmin * (c0 + c1 + c2 + c3) + c1 + 2 * c2 + 3 * c3 <= W:
                    ans = max(ans, _w[0][c0] + _w[1][c1] + _w[2][c2] + _w[0][c3])
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)]
w1 = wv[0][0]
ws = []
for i in range(N+1):
    for j in range(4):
        w = i*(w1+j)
        if w > W:
            break
        ws.append(w)
    if w > W:
        break

dp = [defaultdict(lambda:-float('inf')) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in ws:
        w,v = wv[i]
        dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
print(max(dp[N].values()))

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)]
w1 = wv[0][0]
ws = []
for i in range(N+1):
    for j in range(4):
        w = i*(w1+j)
        if w > W:
            break
        ws.append(w)

dp = [defaultdict(lambda:-float('inf')) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in ws:
        w,v = wv[i]
        dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
print(max(dp[N].values()))

Submission status: Wrong Answer

Solution code:
n,l=map(int,input().split())
dic={0:0}
for _ in range(n):
  w,v=map(int,input().split())
  tmp=list(dic.keys())
  for key in tmp:
    if key+w not in dic:
      dic[key+w]=dic[key]+v
    else:
      dic[key+w]=max(dic[key]+v,dic[key+w])
tmp=sorted(list(dic.keys()))
ans=0
for key in tmp:
  if key>l:
    break
  ans=max(ans,dic[key])
print(ans)

Submission status: Wrong Answer

Solution code:
n,l=map(int,input().split())
dic={0:0}
for _ in range(n):
  w,v=map(int,input().split())
  tmp=list(dic.keys())
  for key in tmp:
    if key+w not in dic:
      dic[key+w]=dic[key]+v
    else:
      dic[key+w]=max(dic[key]+v,dic[key+w])
print(max(dic.values()))

Submission status: Wrong Answer

Solution code:
n,l=map(int,input().split())
dic={0:0}
for _ in range(n):
  w,v=map(int,input().split())
  tmp=list(dic.keys())
  for key in tmp:
    if key+w>l:
      continue
    if key+w not in dic:
      dic[key+w]=dic[key]+v
    else:
      dic[key+w]=max(dic[key]+v,dic[key+w])
print(max(dic.values()))

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
w1,v = map(int,input().split())
wv = [[v],[],[],[]]
for i in range(N-1):
    w,v = map(int,input().split())
    wv[w-w1].append(v)
for i in range(4):
    wv[i]=[0] + sorted(wv[i],reverse=True)
# 累積和
for i in range(4):
    for j in range(1,len(wv[i])):
        wv[i][j] += wv[i][j-1]
ans = 0
hoge = [0,0,0,0]
for i in range(len(wv[0])):
    hoge[0] = wv[0][i]
    if hoge[0] > W:
        break
    for j in range(len(wv[1])):
        hoge[1] = wv[1][j]
        for k in range(len(wv[2])):
            hoge[2] = wv[2][k]
            for l in range(len(wv[3])):
                hoge[3] = wv[3][l]
                if w1*(i+j+k+l)+j+2*k+3*l > W:
                    break
                else:
                    ans = max(ans,sum(hoge))
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
w1,v = map(int,input().split())
wv = [[0,v],[0],[0],[0]]
for i in range(N-1):
    w,v = map(int,input().split())
    wv[w-w1].append(v)
for i in range(4):
    wv[i].sort()
# 累積和
for i in range(4):
    for j in range(1,len(wv[i])):
        wv[i][j] += wv[i][j-1]
ans = 0
hoge = [0,0,0,0]
for i in range(len(wv[0])):
    hoge[0] = wv[0][i]
    if hoge[0] > W:
        break
    for j in range(len(wv[1])):
        hoge[1] = wv[1][j]
        for k in range(len(wv[2])):
            hoge[2] = wv[2][k]
            for l in range(len(wv[3])):
                hoge[3] = wv[3][l]
                if w1*(i+j+k+l)+j+2*k+3*l > W:
                    break
                else:
                    ans = max(ans,sum(hoge))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, W = list(map(int, sys.stdin.readline().split()))
Ws, Vs = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

Ws = np.array(Ws)
Vs = np.array(Vs)

w1 = Ws[0]
ws = np.arange(4) + w1
v1s = np.concatenate([[0], Vs[Ws == ws[0]]])
v2s = np.concatenate([[0], Vs[Ws == ws[1]]])
v3s = np.concatenate([[0], Vs[Ws == ws[2]]])
v4s = np.concatenate([[0], Vs[Ws == ws[3]]])
v1s.sort()
v2s.sort()
v3s.sort()
v4s.sort()
v1s = v1s.cumsum()
v2s = v2s.cumsum()
v3s = v3s.cumsum()
v4s = v4s.cumsum()

counts = np.array(list(itertools.product(
    range(len(v1s)),
    range(len(v2s)),
    range(len(v3s)),
    range(len(v4s))
)))
counts = counts[np.dot(counts, ws) <= W]

sums = v1s[counts[:, 0]] + \
       v2s[counts[:, 1]] + \
       v3s[counts[:, 2]] + \
       v4s[counts[:, 3]]
print(sums.max())

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, W = MI()
    items = [[] for _ in range(4)]
    w0, v0 = MI()
    items[0].append(v0)
    for _ in range(N-1):
        w, v = MI()
        items[w - w0].append(v)
        
    cumsum = [[0] + list(accumulate(items[i])) for i in range(4)]
    ans=0
    for i,c0 in enumerate(cumsum[0]):
        for j,c1 in enumerate(cumsum[1]):
            for k,c2 in enumerate(cumsum[2]):
                s = i * w0 + j * (w0 + 1) + k * (w0 + 2)
                if s <= W:
                    l = min(len(cumsum[3])-1,(W-s)//(w0+3))
                    ans = max(ans, c0 + c1 + c2 +cumsum[3][l])
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, W = MI()
    items = [[] for _ in range(4)]
    w0, v0 = MI()
    items[0].append(v0)
    for _ in range(N-1):
        w, v = MI()
        items[w - w0].append(v)
        
    cumsum = [[0] + list(accumulate(items[i])) for i in range(4)]
    ans=0
    for i in range(len(cumsum[0])):
        for j in range(len(cumsum[1])):
            for k in range(len(cumsum[2])):
                s = i * w0 + j * (w0 + 1) + k * (w0 + 2)
                if s <= W:
                    l = min(len(cumsum[3])-1,(W-s)//(w0+3))
                    ans = max(ans, cumsum[0][i] + cumsum[1][j] + k * cumsum[2][k] + l * cumsum[3][l])
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
wv = {}
for i in range(N):
    w,v = map(int,input().split())
    if w not in wv.keys():
        wv[w] = []
    wv[w].append(v)

for w in wv.keys():
    wv[w] = sorted(wv[w],reverse=True)

wv_ruiseki = {}
for w in wv.keys():
    wv_ruiseki[w] = [0,wv[w][0]]
    for i in range(2,len(wv[w])+1):
        wv_ruiseki[w].append(wv_ruiseki[w][i-1] + wv[w][i-1])


w = []
for i in wv.keys():
    w.append(i)

ans = 0
if len(w) == 1:

    for i in range(len(wv[w[0]])+1):
        if w[0]*i <= W:
            ans = max(ans , wv_ruiseki[w[0]][i])
elif len(w) == 2:

    for i in range(len(wv[w[0]])+1):
        for j in range(len(wv[w[1]])+1):
            if w[0]*i + w[1]*j <= W:
                ans = max(ans , wv_ruiseki[w[0]][i]+ wv_ruiseki[w[1]][j])

elif len(w) == 3:

    for i in range(len(wv[w[0]])+1):
        for j in range(len(wv[w[1]])+1):
            for k in range(len(wv[w[2]])+1):
                if w[0]*i + w[1]*j + w[2]*k <= W:
                    ans = max(ans , wv_ruiseki[w[0]][i]+ wv_ruiseki[w[1]][j] + wv_ruiseki[w[2]][k])
elif len(w) == 4:
    for i in range(len(wv[w[0]])):
        for j in range(len(wv[w[1]])):
            for k in range(len(wv[w[2]])):
                for t in range(len(wv[w[3]])):
                    if w[0]*i + w[1]*j + w[2]*k + w[3]*k <= W:
                        ans = max(ans , wv_ruiseki[w[0]][i]+ wv_ruiseki[w[1]][j] + wv_ruiseki[w[2]][k] + wv_ruiseki[w[3]][t])


print(ans)

Submission status: Wrong Answer

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

dp = [[0 for _ in range(W+1)]for _ in range(N)]
#dp[0][0] = 0
check = [0] * (W+1)
for i in range(N):
      w,v = map(int, input().split())
      check = [0] * (W+1)
      for j in range(W+1):
            if j >= w:
                  if i != 0:
                        if dp[i-1][j] < dp[i][j-w]+v and check[j-w] == 0:
                              dp[i][j] = dp[i][j-w]+v
                              check[j] = 1
                        else:
                              dp[i][j] = dp[i-1][j]
                              #check[j] = check[j-1]
                  else:
                        dp[i][j] = v
                        check[j] = 1
            else:
                  if i != 0:
                        dp[i][j] = dp[i-1][j]
                  else:
                        dp[i][j] = 0
      #print(check)


#print(dp)
print(dp[N-1][W])

Submission status: Wrong Answer

Solution code:
from collections import *

N,W=map(int,input().split())
d=defaultdict(int)
d[0]=0
for i in range(N):
    v,w=map(int,input().split())
    c=d.copy()
    for p,q in c.items():
        if p+w<=W:
            d[p+w]=max(d[p+w],q+v)
print(max(d.values()))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as d
s=d(int)
s[0]=0
n,w=map(int,input().split())
for i in range(n):
    q,v=map(int,input().split())
    c=s.copy()
    for p,r in c.items():
        if p+q<=w:
            s[p+q]=max(s[p+q],s[p]+v)
print(max(s.values()))

Submission status: Wrong Answer

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

N,W = map(int,input().split())
info = []
for i in range(N):
    w,v = map(int,input().split())
    if i == 0:
        w1 = w
    w = w - (w1-1)
    info.append((w,v))
# dp[i][j][k]
# dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-w][k-1])
# dp[0][j][0] = 0
# ans = max(dp[N][j][k] w1*k + j <= W)
dp = [[[0]*(N+1) for _ in range(400)] for _ in range(N+1)]
for i in range(1,N+1):
    w = info[i-1][0]; v = info[i-1][1]
    for j in range(400):
        for k in range(1,N+1):
            dp[i][j][k] = dp[i-1][k][k]
            if j - w >= 0:
                if dp[i][j][k] < dp[i-1][j-w][k-1] + v:
                    dp[i][j][k] = dp[i-1][j-w][k-1] + v
ans = -1
for j in range(400):
    for k in range(N+1):
        if not((w1-1)*k + j <= W):
            continue
        if dp[N][j][k] > ans:
            ans = dp[N][j][k]
print(ans)

Submission status: Wrong Answer

Solution code:
def debug():
    N,W = map(int,input().split())
    info = [list(map(int,input().split())) for _ in range(N)]
    dp = [[0]*(W+1) for _ in range(N+1)]
    for i in range(1,N+1):
        w = info[i-1][0]; v = info[i-1][1]
        for j in range(W+1):
            if j-w >= 0:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
            else:
                dp[i][j] = dp[i-1][j]
    ans = dp[N][W]
    print(ans)

def main():
    N,W = map(int,input().split())
    info = []
    for i in range(N):
        w,v = map(int,input().split())
        if i == 0:
            w1 = w
        w = w - (w1-1)
        info.append((w,v))
    # dp[i][j][k]
    # dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-w][k-1])
    # dp[0][j][0] = 0
    # ans = max(dp[N][j][k] w1*k + j <= W)
    dp = [[[0]*(N+1) for _ in range(400)] for _ in range(N+1)]
    for i in range(1,N+1):
        w = info[i-1][0]; v = info[i-1][1]
        for j in range(400):
            for k in range(1,N+1):
                if j - w >= 0:
                    dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-w][k-1] + v)
                else:
                    dp[i][j][k] = dp[i-1][j][k]
    ans = -1
    for j in range(400):
        for k in range(N+1):
            if dp[N][j][k] == 11:
                print(j,k)
            if not((w1-1)*k + j <= W):
                continue
            if dp[N][j][k] > ans:
                ans = dp[N][j][k]
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
n,W = map(int,input().split())
a = {}
for i in range(n):
    w,v = map(int,input().split())
    a.setdefault(w, []).append(v)

we = [0]*4
va = []
num = [0]*4
for i,[k,v] in enumerate(a.items()):
    we[i] = k
    va.append(sorted(v,reverse=True))
    num[i] = len(v)
for i in range(4-len(va)):
    va.append([0])

ans = -float('inf')
for i in range(26):
    for j in range(26):
        for k in range(26):
            for l in range(26):
                if i <= num[0] and j <= num[1] and k <= num[2] and l <= num[3]:
                    if we[0]*i + we[1]*j + we[2]*k + we[3]*l <= W:
                        total = 0
                        for im,m in enumerate([i,j,k,l]):
                            total += sum(va[im][:m])
                        ans = max(ans, total)
print(ans)

Submission status: Wrong Answer

Solution code:
n,W = map(int,input().split())
a = {}
for i in range(n):
    w,v = map(int,input().split())
    a.setdefault(w, []).append(v)
we = [0]*4
va = []
num = [0]*4
for i,[k,v] in enumerate(a.items()):
    we[i] = k
    va.append(sorted(v,reverse=True))
    num[i] = len(v)
for i in range(4-len(va)):
    va.append([0])

ans = -float('inf')
for i in range(25):
    for j in range(25):
        for k in range(25):
            for l in range(25):
                if i <= num[0] and j <= num[1] and k <= num[2] and l <= num[3]:
                    if we[0]*i + we[1]*j + we[2]*k + we[3]*l <= W:
                        total = 0
                        for im,m in enumerate([i,j,k,l]):
                            total += sum(va[im][:m])
                        ans = max(ans, total)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right


def main():
    N, W = map(int, input().split())
    dp = {0: 0}
    for i in range(N):
        w, v = map(int, input().split())
        nxt = {}
        for k in dp:
            if k+w <= W:
                nxt[k+w] = max(dp[k] + v, dp[k+w] if k+w in dp else 0)
        dp.update(nxt)
    keys = list(dp.keys())
    keys.sort()
    i = bisect_right(keys, W) - 1
    print(dp[keys[i]])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
""""
n,T = LI()
ans = 0
t = LI()
for i in range(n-1):
    ans += min(T,t[i+1]-t[i])
ans += T
print(ans)
"""

#D
n,w = LI()
g = LIR(n)
l = [[] for i in range(4)]
for W,v in g:
    l[W-g[0][0]].append(v)
    l[W-g[0][0]].sort()
l0 = len(l[0])
l1 = len(l[1])
l2 = len(l[2])
l3 = len(l[3])
for i in range(l0-1):
    l[0][i+1] += l[0][i]
l[0].insert(0,0)
for i in range(l1-1):
    l[1][i+1] += l[1][i]
l[1].insert(0,0)
for i in range(l2-1):
    l[2][i+1] += l[2][i]
l[2].insert(0,0)
for i in range(l3-1):
    l[3][i+1] += l[3][i]
l[3].insert(0,0)
ans = 0
for i in range(l0+1):
    for j in range(l1+1):
        for k in range(l2+1):
            for m in range(l3+1):
                if i*g[0][0]+j*(g[0][0]+1)+k*(g[0][0]+2)+m*(g[0][0]+3) <= w:
                    ans = max(ans,l[0][i]+l[1][j]+l[2][k]+l[3][m])
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T