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())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(N):
        for j in range(3*N):
            if dp[i][n][j] == -1: continue
            # if j + n*ws[0] > W: continue
            # print("check",i,n,j,v)
            dp[i+1][n+1][j] = max(dp[i+1][n+1][j], dp[i][n+1][j])
            dp[i+1][n+1][j+w] = max(dp[i][n+1][j+w], dp[i][n][j] + v)
ans= 0
for i,As in enumerate(dp[N]):
    w = W - i*ws[0]
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i,-1,-1):
        for j in range(3*N):
            if dp[i][n][j] == -1: continue
            # if j + n*ws[0] > W: continue
            # print("check",i,n,j,v)
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
            dp[i+1][n+1][j+w] = max(dp[i][n+1][j+w], dp[i][n][j] + v)
ans= 0
for i,As in enumerate(dp[N]):
    w = W - i*ws[0]
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N):
            if dp[i][n][j] == -1: continue
            if j + n*ws[0] > W: continue
            # print("check",i,n,j,v)
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
            dp[i+1][n+1][j+w] = max(dp[i][n+1][j+w], dp[i][n][j] + v)
ans= 0
for i,As in enumerate(dp[N]):
    w = W - i*ws[0]
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N):
            if dp[i][n][j] == -1: continue
            if j + n*ws[0] > W: continue
            # print("check",i,n,j,v)
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
            dp[i+1][n+1][j+w] = max(dp[i][n][j+w], dp[i][n][j] + v)
ans= 0
for i,As in enumerate(dp[N]):
    w = W - i*ws[0]
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(min(sum(ws_m),W-n*ws[0])+1):
            if dp[i][n][j] == -1: continue
            if j + n*ws[0] > W: continue
            # print("check",i,n,j,v)
            dp[i+1][n+1][j+w] = max(dp[i][n][j+w], dp[i][n][j] + v)
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
ans= 0
for i,As in enumerate(dp[N]):
    w = min(W - i*ws[0], sum(ws))
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(min(sum(ws_m),W-n*ws[0])+1):
            if dp[i][n][j] == -1: continue
            if j + n*ws[0] > W: continue
            # print("check",i,n,j,v)
            dp[i+1][n+1][j+w] = max(dp[i][n][j+w], dp[i][n][j] + v)
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
ans= 0
for i,As in enumerate(dp[N]):
    w = W - i*ws[0]
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N):
            if dp[i][n][j] == -1: continue
            if j + n*ws[0] > W: continue
            # print("check",i,n,j,v)
            dp[i+1][n+1][j+w] = max(dp[i][n][j+w], dp[i][n][j] + v)
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
ans= 0
for i,As in enumerate(dp[N]):
    w = W - i*ws[0]
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(N):
        for j in range(3*N):
            if dp[i][n][j] == -1: continue
            if dp[i][n][j]+v >= dp[i][n][j+w]:
                # print("aa",i,n,j,v)
                dp[i+1][n+1][j+w] = dp[i][n][j] + v
            else:
                dp[i+1][n][j+w] = dp[i][n][j+w]
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
    # print(dp[i])

# for i in range(N+1):
    # print("i個選んだやつ",dp[N][i])
ans= 0
for i,As in enumerate(dp[N]):
    w = min(sum(ws_m),W - i*ws[0])
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]
s_w = sum(ws_m)
"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(N):
        for j in range(s_w):
            if dp[i][n][j] == -1: continue
            if dp[i][n][j]+v >= dp[i][n][j+w]:
                # print("aa",i,n,j,v)
                dp[i+1][n+1][j+w] = dp[i][n][j] + v
            else:
                dp[i+1][n][j+w] = dp[i][n][j+w]
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
    # print(dp[i])

# for i in range(N+1):
    # print("i個選んだやつ",dp[N][i])
ans= 0
for i,As in enumerate(dp[N]):
    w = W - i*ws[0]
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(N):
        for j in range(3*N):
            if dp[i][n][j] == -1: continue
            if dp[i][n][j]+v >= dp[i][n][j+w]:
                # print("aa",i,n,j,v)
                dp[i+1][n+1][j+w] = dp[i][n][j] + v
            else:
                dp[i+1][n][j+w] = dp[i][n][j+w]
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
    # print(dp[i])

# for i in range(N+1):
    # print("i個選んだやつ",dp[N][i])
ans= 0
for i,As in enumerate(dp[N]):
    w = W - i*ws[0]
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(N):
        for j in range(N):
            if dp[i][n][j] == -1: continue
            if dp[i][n][j]+v >= dp[i][n][j+w]:
                # print("aa",i,n,j,v)
                dp[i+1][n+1][j+w] = dp[i][n][j] + v
            else:
                dp[i+1][n][j+w] = dp[i][n][j+w]
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
    # print(dp[i])

# for i in range(N+1):
    # print("i個選んだやつ",dp[N][i])
ans= 0
for i,As in enumerate(dp[N]):
    w = W - i*ws[0]
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[-1]*(3*N+1) for i in range(N+1)]
dp[0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):    
    dp[i+1][:] = dp[i][:]
    for j in range(len(dp[i])):
        if dp[i][j] == -1:continue
        dp[i+1][j+w] = max(dp[i][j]+v, dp[i][j+w])
    # print(dp)

# print(dp[N][W-N*ws_m[0]])

dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    # print(i,w,v)
    for n in range(N):
        # dp[i+1][n][:] = dp[i][n][:]
        for j in range(N):
            if dp[i][n][j] == -1:continue
            if dp[i][n][j]+v >= dp[i][n][j+w]:
                # print("aa",i,n,j,v)
                dp[i+1][n+1][j+w] = dp[i][n][j] + v
            else:
                dp[i+1][n][j+w] = dp[i][n][j+w]
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
    # print(dp[i])

# for i in range(N+1):
    # print("i個選んだやつ",dp[N][i])
anss = dp[N]
a = 0
for i,ans in enumerate(anss):
    w = W - i*ws[0]
    if w > 0:
        a = max(a,max(ans[:w+1]))
print(a)

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]

from collections import defaultdict

dp = [defaultdict(int) for _ in range(N + 1)]
dp[0][0] = 0

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

print(dp[-1][W])

Submission status: Wrong Answer

Solution code:
#誤答（たくさん取れる）
#12:11
n,u = map(int,input().split())
w0,v0 = map(int,input().split())
vn = [v0,0,0,0]
wn = [w0,w0+1,w0+2,w0+3]
for _ in range(n-1):
  w,v = map(int,input().split())
  vn[w-w0] = max(vn[w-w0],v)
#print(wn)
#print(vn)
can = []
from itertools import permutations as perm
for per in perm(range(4)):
  #print(per)
  utmp = int(u)
  vtmp = vn[:]
  wtmp = wn[:]
  now = 0
  for d in range(4):
    wtmpd = wtmp[d]
    tmp = utmp // wtmpd
    vtmpd = vtmp[per[d]]
    if vtmpd <= 0 or wtmpd == 0:
      continue
    now += tmp * vtmpd
    utmp -= tmp * wtmpd
    #print(tmp,d)
    for di in range(4):
      if wtmp[di] >= wtmpd:
        vtmp[di] -= vtmpd
        wtmp[di] -= wtmpd
  #print(now)
  can.append(now)
print(max(can))

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
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()
    WV=LLIN(N)
    W0 = WV[0][0]
    for i,(w,v) in enumerate(WV):
        WV[i][0] = w-W0
    WV.sort(key=lambda x: x[1], reverse=True)
    cumsum = [0]*N
    for i,(w,v) in enumerate(WV):
        cumsum[i]=cumsum[i-1]+v

    dp = [[0]*(N*3+1) for _ in range(N+1)]
    for i in range(N):
        for k in range(1,N+1)[::-1]:
            for w in range(N*3+1):
                if w>=WV[i][0]:
                    dp[k][w] = max(dp[k][w], dp[k-1][w-WV[i][0]] + WV[i][1])

    ans = 0 
    for k in range(1,N+1):
        W_k = W-W0*k
        if W_k>=N*3:
            ans = max(ans, cumsum[k-1])
            continue
        if W_k<=0:
            break   
        ans = max(ans, dp[k][W_k])
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, W = (int(i) for i in input().split())
    WV = [[int(i) for i in input().split()] for j in range(N)]
    for i in range(1, N):
        WV[i][0] -= WV[0][0]
    w_base = WV[0][0]
    WV[0][0] = 0
    V = {i: [] for i in range(4)}
    for w, v in WV:
        V[w].append(v)
    for i in range(4):
        V[i].sort(reverse=True)
    ans = 0
    from itertools import product
    for p in product(range(len(V[0])), range(len(V[1])),
                     range(len(V[2])), range(len(V[3]))):
        w_cur = w_base*p[0] + (w_base+1)*p[1] + \
            (w_base+2)*p[2] + (w_base+3)*p[3]
        if W < w_cur:
            continue
        ans = max(ans, sum(sum(V[i][:min(p[i], len(V[i]))]) for i in range(4)))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, W = (int(i) for i in input().split())
    WV = [[int(i) for i in input().split()] for j in range(N)]
    for i in range(1, N):
        WV[i][0] -= WV[0][0]
    w_base = WV[0][0]
    WV[0][0] = 0
    V = {i: [] for i in range(4)}
    for w, v in WV:
        V[w].append(v)
    for i in range(4):
        V[i].sort(reverse=True)
    ans = 0
    from itertools import product
    for p in product(range(26), repeat=4):
        w_cur = w_base*p[0] + (w_base+1)*p[1] + \
            (w_base+2)*p[2] + (w_base+3)*p[3]
        if W < w_cur:
            continue
        ans = max(ans, sum(sum(V[i][:min(p[i], len(V[i]))]) for i in range(4)))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, W = (int(i) for i in input().split())
    WV = [[int(i) for i in input().split()] for j in range(N)]
    for i in range(1, N):
        WV[i][0] -= WV[0][0]
    w_base = WV[0][0]
    WV[0][0] = 0
    V = {i: [] for i in range(4)}
    for w, v in WV:
        V[w].append(v)
    for i in range(4):
        V[i].sort(reverse=True)
    ans = 0
    from itertools import product
    for p in product(range(26), repeat=4):
        w_cur = w_base*p[0] + (w_base+1)*p[1] + \
            (w_base+2)*p[2] + (w_base+3)*p[3]
        if W < w_cur:
            continue
        ans = max(ans, sum(sum(V[i][:p[i]]) for i in range(4)))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

N, W = map(int, input().split())
d = {i: [0] for i in range(4)}
for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        w0 = w
    w -= w0
    d[w].append(v)

wv = [[] for _ in range(4)]
for k, v in d.items():
    v.sort()
    wv[k] = tuple(accumulate(v))

# w1をc1こ入れる
# w2をc2個入れる...
ans = 0
for c0, v0 in enumerate(wv[0]):
    for c1, v1 in enumerate(wv[1]):
        for c2, v2 in enumerate(wv[2]):
            for c3, v3 in enumerate(wv[3]):
                weight = w0 * (c0 + c1 + c2 + c3) + c1 + c2 * 2 + c3 * 3
                val = v0 + v1 + v2 + v3
                if weight > W:
                    continue
                ans = max(ans, val)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_right

N,W = LI()
w,v = LIR(N,2)

w_list = []
for i in range(N+1):
    for j in range(i*w[0],i*(w[0]+3)+1):
        w_list.append(j)
w_list = sorted(list(set(w_list)))
M = len(w_list)

dw = defaultdict(int)
dwi = defaultdict(int)
temp = 0
for wl in w_list:
    dw[temp] = wl
    dwi[wl] = temp
    temp += 1

dp = [[0]*M for _ in range(N)]
for i in range(1,N):
    for j in range(M):
        dp[i][j] = dp[i-1][j]
        x = dw[j]-w[i]
        if x >= 0:
            dp[i][j] = max(dp[i][j], dp[i-1][dwi[x]]+v[i])

p = bisect_right(w_list,W)
print(dp[N-1][p-1])

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_right

N,W = LI()
w,v = LIR(N,2)

w_list = []
for i in range(N+1):
    for j in range(i*w[0],i*(w[0]+3)+1):
        w_list.append(j)
w_list = sorted(list(set(w_list)))
M = len(w_list)

dw = defaultdict(int)
dwi = defaultdict(int)
temp = 0
for wl in w_list:
    dw[temp] = wl
    dwi[wl] = temp
    temp += 1

dp = [[0]*M for _ in range(N)]
for i in range(N):
    for j in range(M):
        dp[i][j] = dp[i-1][j]
        x = dw[j]-w[i]
        if x >= 0:
            dp[i][j] = max(dp[i][j], dp[i-1][dwi[x]]+v[i])

p = bisect_right(w_list,W)
print(dp[N-1][p-1])

Submission status: Wrong Answer

Solution code:
INFTY = 10**11
N,W = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
dp = [[[-INFTY for _ in range(3*(N-1)+1)] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    for j in range(1,i+1):
        for k in range(3*(N-1)+1):
            if k<=3*j:
                dp[i][j][k] = dp[i-1][j][k]
                if k>=X[i-1][0]-X[0][0]:
                    dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-X[i-1][0]+X[0][0]]+X[i-1][1])
cmax = 0
for j in range(1,N+1):
    if 3*(N-1)>=W-j*X[0][0]>=0:
        for k in range(W-j*X[0][0]+1):
            cmax = max(cmax,dp[N][j][k])
print(cmax)

Submission status: Wrong Answer

Solution code:
INFTY = 10**10
N,W = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
dp = [[[-INFTY for _ in range(3*(N-1)+1)] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    for j in range(1,i+1):
        for k in range(3*(N-1)+1):
            if k<=3*j:
                dp[i][j][k] = dp[i-1][j][k]
                if k>=X[i-1][0]-X[0][0]:
                    dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-X[i-1][0]+X[0][0]]+X[i-1][1])
cmax = 0
for j in range(1,N+1):
    if 3*(N-1)>=W-j*X[0][0]>=0:
        for k in range(W-j*X[0][0]+1):
            cmax = max(cmax,dp[N][j][k])
print(cmax)

Submission status: Wrong Answer

Solution code:
INFTY = 10**10
N,W = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
dp = [[[-INFTY for _ in range(3*(N-1)+1)] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    for j in range(1,i+1):
        for k in range(3*(N-1)+1):
            dp[i][j][k] = dp[i-1][j][k]
            if k>=X[i-1][0]-X[0][0]:
                dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-X[i-1][0]+X[0][0]]+X[i-1][1])
cmax = 0
for j in range(1,N+1):
    if 3*(N-1)>=W-j*X[0][0]>=0:
        for k in range(W-j*X[0][0]+1):
            cmax = max(cmax,dp[N][j][k])
print(cmax)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
dic = {"0":[],"1":[],"2":[],"3":[]}
for i in range(N):
  w,v = map(int,input().split())
  if i == 0:
    Min = w
  if w == Min:
    dic["0"].append(v)
  elif w == Min+1:
    dic["1"].append(v)
  elif w == Min+2:
    dic["2"].append(v)
  elif w == Min+3:
    dic["3"].append(v)
    
dic["0"].sort()
dic["1"].sort()
dic["2"].sort()
dic["3"].sort()

ans = 0
for i in range(len(dic["0"])+1):
  for j in range(len(dic["1"])+1):
    for k in range(len(dic["2"])+1):
      for l in range(len(dic["3"])+1): 
        a = int(sum(dic["0"][:i])+sum(dic["1"][:j])+sum(dic["2"][:k])+sum(dic["3"][:l])) 
        b = int(i*Min+j*(Min+1)+k*(Min+2)+l*(Min+3))
        if a > ans and b <= W:
          ans = a
print(int(ans))

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
dic = {"0":[],"1":[],"2":[],"3":[]}
for i in range(N):
  w,v = map(int,input().split())
  if i == 0:
    Min = w
  if w == Min:
    dic["0"].append(v)
  elif w == Min+1:
    dic["1"].append(v)
  elif w == Min+2:
    dic["2"].append(v)
  elif w == Min+3:
    dic["3"].append(v)
    
dic["0"].sort()
dic["1"].sort()
dic["2"].sort()
dic["3"].sort()

ans = 0
for i in range(len(dic["0"])+1):
  for j in range(len(dic["1"])+1):
    for k in range(len(dic["2"])+1):
      for l in range(len(dic["3"])+1): 
        a = sum(dic["0"][:i])+sum(dic["1"][:j])+sum(dic["2"][:k])+sum(dic["3"][:l]) 
        b = i*Min+j*(Min+1)+k*(Min+2)+l*(Min+3)
        if a > ans and b <= W:
          ans = a
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
D = {0: [0]}
for i in range(N):
  w, v = map(int, input().split())
  A = [[i, D[i][len(D[i])-1]] for i in D]
  for j in A:
    if j[0] + w <= W:
      if j[0] + w in D:
        D[j[0]+w].append(j[1] + v)
      else:
        D[j[0]+w] = [j[1]+v]
for i in D:
  D[i] = max(D[i])
print(max(D[i] for i in D))

Submission status: Wrong Answer

Solution code:
import bisect
N,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(N)]
w1=wv[0][0]

Wlist=[0]+[j*(w1+i) for j in range(1,N+1) for i in range(3*j+1)]
Wlist=sorted(set(Wlist))
LW=len(Wlist)
dp=[[0]*LW for _ in range(N+1)]
#dp[i][j]:N個の物に対して強度(Wlist[j])のバッグ

for i in range(1,N+1):
  w,v=wv[i-1]
  for j in range(LW):
    if w<=Wlist[j]:      
      ind=bisect.bisect_right(Wlist,Wlist[j]-w)-1
      dp[i][j]=max(dp[i-1][j],dp[i-1][ind]+v)
    else:
      dp[i][j]=dp[i-1][j]

ind=bisect.bisect_right(Wlist,W)-1
print(dp[N][ind])

Submission status: Wrong Answer

Solution code:
import bisect
N,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(N)]
w1=wv[0][0]

Wlist=[0]+[j*(w1+i) for j in range(1,N+1) for i in range(4)]
Wlist=sorted(set(Wlist))
LW=len(Wlist)
dp=[[0]*LW for _ in range(N+1)]
#dp[i][j]:N個の物に対して強度(Wlist[j])のバッグ


for i in range(1,N+1):
  w,v=wv[i-1]
  for j in range(LW):
    if w<=Wlist[j]:      
      ind=bisect.bisect_right(Wlist,Wlist[j]-w)-1
      
      dp[i][j]=max(dp[i-1][j],dp[i-1][ind]+v)
    else:
      dp[i][j]=dp[i-1][j]

ind=bisect.bisect_right(Wlist,W)-1
print(dp[N][ind])

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(N)]
w1=wv[0][0]
wm=max([i[0] for i in wv])

Wlist=[0]+[j*(w1+i) for j in range(1,N+1) for i in range(4)]
dp=[[0]*(4*N+1) for _ in range(N+1)]
#dp[i][j]:N個の物に対して強度(Wlist[j])のバッグ

for i in range(1,N+1):
  w,v=wv[i-1]
  for j in range(4*N+1):
    if w<=Wlist[j]:
      
      ind=0
      d=float("inf")
      for k in range(4*N+1):
        if (Wlist[j]-w)>=Wlist[k] and (Wlist[j]-w)-Wlist[k]<d:
          d=(Wlist[j]-w)-Wlist[k]
          ind=k
      
      dp[i][j]=max(dp[i-1][j],dp[i-1][ind]+v)
    else:
      dp[i][j]=dp[i-1][j]

ind=0
d=float("inf")
for k in range(4*N+1):
  if W>=Wlist[k] and W-Wlist[k]<d:
    d=W-Wlist[k]
    ind=k
print(dp[N][ind])

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, W = list(map(int, readline().split()))
    wv = [list(map(int, readline().split())) for _ in range(n)]
    mt = 10 ** 10
    for w, v in wv:
        mt = min(mt, w)
    wv0 = []
    wv1 = []
    wv2 = []
    for w, v in wv:
        if w - mt == 0:
            wv0.append(v)
        elif w - mt == 1:
            wv1.append(v)
        elif w - mt == 2:
            wv2.append(v)
    wv0.sort(reverse=True)
    wv0.insert(0, 0)
    wv1.sort(reverse=True)
    wv1.insert(0, 0)
    wv2.sort(reverse=True)
    wv2.insert(0, 0)
    mtt = 0
    dp0 = [0, 0]
    for v0 in wv0:
        dp0[0] += mt if v0 != 0 else 0
        dp0[1] += v0
        if dp0[0] <= W:
            mtt = max(mtt, dp0[1])
        dp1 = [dp0[0], dp0[1]]
        for v1 in wv1:
            dp1[0] += (mt + 1) if v1 != 0 else 0
            dp1[1] += v1
            if dp1[0] <= W:
                mtt = max(mtt, dp1[1])
            dp2 = [dp1[0], dp1[1]]
            for v2 in wv2:
                dp2[0] += (mt + 2) if v2 != 0 else 0
                dp2[1] += v2
                if dp2[0] <= W:
                    mtt = max(mtt, dp2[1])
    print(mtt)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

    ans = 0

    for i in range(len(d[w1])+1):
        for j in range(len(d[w1+1])+1):
            for k in range(len(d[w1+2])+1):
                for l in range(len(d[w1+3])+1):
                    tmp = sum(d[w1][:i]) + sum(d[w1+1][:j]) + sum(d[w1+2][:k]) + sum(d[w1+3][:l])

                    if w1 * i + (w1+1) * j + (w1+2) * k + (w1+3) * l <= W:
                        ans = max(ans,tmp)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, W = map(int, input().split())
dp = [[[0] * 301 for _ in range(n + 1)] for _ in range(n + 1)]
li = [list(map(int, input().split())) for _ in range(n)]
p = li[0][0]
for i, x in enumerate(li):
    w, v = x
    w -= p
    for j in range(i + 1):
        for k in range(301):
            if k >= w:
                if dp[i][j][k - w] + v > dp[i][j][k]:
                    dp[i + 1][j + 1][k] = dp[i][j][k - w] + v
                else:
                    dp[i + 1][j + 1][k] = dp[i][j + 1][k]
            else:
                dp[i + 1][j + 1][k] = dp[i][j + 1][k]
ans = 0
for i in range(n + 1):
    for k in range(301):
        if i * p + k <= W:
            ans = max(dp[n][i][k], ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n, W = map(int, input().split())
dp = [[[0] * 301 for _ in range(n + 1)] for _ in range(n + 1)]
li = [list(map(int, input().split())) for _ in range(n)]
p = li[0][0]
for i, x in enumerate(li):
    w, v = x
    w -= p
    for j in range(i + 1):
        for k in range(301):
            if k >= w:
                if dp[i][j][k - w] + v > dp[i][j][k] and j + 1 <= 300:
                    dp[i + 1][j + 1][k] = max(dp[i + 1][j + 1][k],
                                              dp[i][j][k - w] + v)
                else:
                    dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k])
            else:
                dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k])
ans = 0
for i in range(n + 1):
    for k in range(301):
        if i * p + k <= W:
            ans = max(dp[n][i][k], ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n, W = map(int, input().split())
dp = [[[0] * 301 for _ in range(n + 1)] for _ in range(n + 1)]
li = [list(map(int, input().split())) for _ in range(n)]
p = li[0][0]
for i, x in enumerate(li):
    w, v = x
    w -= p
    for j in range(i + 1):
        for k in range(301):
            if k >= w:
                if dp[i][j][k - w] + v > dp[i][j][k]:
                    dp[i + 1][j + 1][k] = dp[i][j][k - w] + v
                else:
                    dp[i + 1][j][k] = dp[i][j][k]
            else:
                dp[i + 1][j][k] = dp[i][j][k]
ans = 0
for i in range(n + 1):
    for k in range(301):
        if i * p + k <= W:
            ans = max(dp[n][i][k], ans)
print(ans)