Submission #8522117

---

Source Code Expand

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 Info

Judge Result