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,m=map(int,input().split())
w=[0]*n 
v=[0]*n
from  collections import defaultdict 
from collections import Counter

d=defaultdict(lambda :0)
l=[]
for i in range(n):
    a,b=map(int,input().split())
    w[i]=a  
    v[i]=b 
a=min(w)
c=Counter(w)
#print(a)
cnt1=c[a]
#print(c)
v1=[v[i] for i in range(n) if w[i]==a]
v1.sort(reverse=1)
cnt2=c[a+1]
v2=[v[i] for i in range(n) if w[i]==a+1]
cnt3=c[a+2]
v3=[v[i] for i in range(n) if w[i]==a+2]
v2.sort(reverse=1)
v3.sort(reverse=1)
#print(cnt1)
pv1=[0]*(cnt1+1)
pv1[0]=0
if cnt2==0:
    v2=[-1]
if cnt3==0:
    v3=[-1]
for i in range(1,cnt1+1):
    pv1[i]=pv1[i-1]+v1[i-1]
pv2=[0]*(cnt2+1)  
pv2[0]=0
for i in range(1,cnt2+1):
    pv2[i]=pv2[i-1]+v2[i-1]
pv3=[0]*(cnt3+1) 
pv3[0]=0
for i in range(1,cnt3+1):
    pv3[i]=pv3[i-1]+v3[i-1]
ans=0 
for i in range(0,cnt1+1):
    for j in range(0,cnt2+1):
        for k in range(0,cnt3+1):
            if (i)*a+(j)*(a+1)+(k)*(a+2)<=m:
                ans=max(ans,pv1[i]+pv2[j]+pv3[k])
print(ans)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
w=[0]*N;v=[0]*N

for i in range(N):
    w[i], v[i] = map(int,input().split())
minW=w[0]
for i in range(N):
    w[i] -= minW - 1 # w[i] = 1~4
dp=[[0]*(5*N+1) for _ in range(N+1)]

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

ans=0
for i in range(5*N):
    if i+minW <= W: ans=max(ans,dp[N][i])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,m=map(int,input().split())
d=defaultdict(int)
d[0]=0
for _ in range(n):
       w,u=map(int,input().split())
       for i in d.copy():
              j=d[i]
              if i+w<=m:d[i+w]=max(d[i+w],j+u)
print(max(d[i]for i in d))

Submission status: Wrong Answer

Solution code:

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

dic = {}
dic[0] = 0

for i in range(N):

    odic = dic.copy()

    w,v = map(int,input().split())

    for j in odic:

        if j + w not in dic and j+w <= W:
            dic[j+w] = dic[j] + v

        elif j+w <= W:
            dic[j+w] = max(dic[j]+v,dic[j+w])

ans = 0

for i in dic:
    ans = max(ans,dic[i])

print (ans)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
ans=0
w=[0 for i in range(N)]
v=[0 for i in range(N)]
t=[[0] for _ in range(4)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
    t[w[i]-w[0]].append(v[i])
for i in range(4):
    t[i].sort(reverse=True)
for i in range(len(t[0])+1):
    for j in range(len(t[1])+1):
        for k in range(len(t[2])+1):
            for m in  range(len(t[3])+1):
                if  w[0]*i+w[1]*j + w[2]*k + w[3]*m <=W:
                    a=0
                    if i!=0:
                        a+=sum(t[0][:i])
                    if j!=0:
                        a+=sum(t[1][:j])
                    if k!=0:
                        a+=sum(t[2][:k])
                    if m!=0:
                        a+=sum(t[3][:m])
                    ans=max(ans,a)
print(ans)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
ans=0
w=[0 for i in range(N)]
v=[0 for i in range(N)]
t=[[0] for _ in range(4)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
    t[w[i]-w[0]].append(v[i])
for i in range(4):
    t[i].sort(reverse=True)
for i in range(len(t[0])+1):
    for j in range(len(t[1])+1):
        for k in range(len(t[2])+1):
            for m in  range(len(t[3])+1):
                if  w[0]*i+w[1]*j + w[2]*k + w[3]*m <=W:
                    a=0
                    if i!=0:
                        a+=sum(t[0][:i])
                    if j!=0:
                        a+=sum(t[1][:j])
                    if k!=0:
                        a+=sum(t[2][:k])
                    if m!=0:
                        a+=sum(t[3][:m])
                    ans=max(ans,sum(t[0][:i])+sum(t[1][:j]) + sum(t[2][:k])+sum(t[3][:m]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
ans=0
w=[0 for i in range(N)]
v=[0 for i in range(N)]
t=[[0] for _ in range(4)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
    t[w[i]-w[0]].append(v[i])
for i in range(4):
    t[i].sort(reverse=True)
for i in range(len(t[0])+1):
    for j in range(len(t[1])+1):
        for k in range(len(t[2])+1):
            for m in  range(len(t[3])+1):
                if  w[0]*i+w[1]*j + w[2]*k + w[3]*m <=W:
                    ans=max(ans,sum(t[0][:i])+sum(t[1][:j]) + sum(t[2][:k])+sum(t[3][:m]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
ans=0
w=[0 for i in range(N)]
v=[0 for i in range(N)]
t=[[] for _ in range(4)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
    t[w[i]-w[0]].append(v[i])
for i in range(4):
    t[i].sort(reverse=True)
for i in range(len(t[0])+1):
    for j in range(len(t[1])+1):
        for k in range(len(t[2])+1):
            for m in  range(len(t[3])+1):
                if  w[0]*i+w[1]*j + w[2]*k + w[3]*m <=W:
                    ans=max(ans,sum(t[0][:i])+sum(t[1][:j]) + sum(t[2][:k])+sum(t[3][:m]))
print(ans)

Submission status: Wrong Answer

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

items = [0]*N
for i in range(N):
  w, v = map(int, input().split())
  items[i] = w, v

def key(wv):
  w, v = wv
  return -v, w

items = sorted(items, key=key)
#print(items)
answer = 0
for w, v in items:
  if W - w < 0:
    continue
  W -= w
  answer += v
print(answer)
#for i in range(1,N+1):  print(WV[i-1],*dp[i],sep="\t")

Submission status: Wrong Answer

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

def main():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]

    base_w = wv[0][0]
    dic = {wv[0][0]:[], wv[0][0]+1:[], wv[0][0]+2:[], wv[0][0]+3:[]}
    for i in range(N):
        w, v = wv[i]
        dic[w].append(v)
    
    wv = list(dic.items())
    tmp = [[0] for i in range(4)]
    for i in range(4):
        num, l = wv[i]
        l = sorted(l, reverse=True)
        for j in range(1, len(l)):
            l[j] += l[j-1]
        tmp[i] += l


    ans = 0
    for i in range(len(tmp[0])):
        now_w = base_w * i
        # if now_w > W:
        #     break
        for j in range(len(tmp[1])):
            now_w1 = now_w + (base_w + 1) * j
            # if now_w > W:
            #     break
            for k in range(len(tmp[2])):
                now_w2 = now_w1 + (base_w + 2) * k
                # if now_w > W:
                #     break
                for l in range(len(tmp[3])):
                    now_w3 = now_w2 + (base_w + 3) * l
                    if now_w3 > W:
                        break
                    else:
                        val = tmp[0][i] + tmp[1][j] + tmp[2][k] + tmp[3][l]
                        if ans < val:
                            ans = val
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]

    base_w = wv[0][0]
    dic = {wv[0][0]:[], wv[0][0]+1:[], wv[0][0]+2:[], wv[0][0]+3:[]}
    for i in range(N):
        w, v = wv[i]
        dic[w].append(v)
    
    wv = list(dic.items())
    tmp = [[0] for i in range(4)]
    for i in range(4):
        num, l = wv[i]
        l = sorted(l, reverse=True)
        for j in range(1, len(l)):
            l[j] += l[j-1]
        tmp[i] += l


    ans = 0
    for i in range(len(tmp[0])):
        now_w = base_w * i
        # if now_w > W:
        #     break
        for j in range(len(tmp[1])):
            now_w1 = now_w + (base_w + 1) * j
            # if now_w > W:
            #     break
            for k in range(len(tmp[2])):
                now_w2 = now_w1 + (base_w + 2) * k
                # if now_w > W:
                #     break
                for l in range(len(tmp[3])):
                    now_w3 = now_w2 + (base_w + 3) * l
                    if now_w3 > W:
                        break
                    else:
                        val = tmp[0][i] + tmp[1][j] + tmp[2][k] + tmp[3][l]
                        if ans < val:
                            ans = val
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]

    base_w = wv[0][0]
    dic = {wv[0][0]:[], wv[0][0]+1:[], wv[0][0]+2:[], wv[0][0]+3:[]}
    for i in range(N):
        w, v = wv[i]
        dic[w].append(v)
    
    wv = list(dic.items())
    tmp = [None] * 4
    for i in range(4):
        num, l = wv[i]
        l = sorted(l, reverse=True)
        for j in range(1, len(l)):
            l[j] += l[j-1]
        tmp[i] = [0] + l


    ans = 0
    for i in range(len(tmp[0])):
        now_w = base_w * i
        # if now_w > W:
        #     break
        for j in range(len(tmp[1])):
            now_w1 = now_w + (base_w + 1) * j
            # if now_w > W:
            #     break
            for k in range(len(tmp[2])):
                now_w2 = now_w1 + (base_w + 2) * k
                # if now_w > W:
                #     break
                for l in range(len(tmp[3])):
                    now_w3 = now_w2 + (base_w + 3) * l
                    if now_w3 > W:
                        break
                    else:
                        val = tmp[0][i] + tmp[1][j] + tmp[2][k] + tmp[3][l]
                        if ans < val:
                            ans = val
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]

    base_w = wv[0][0]
    dic = {wv[0][0]:[], wv[0][0]+1:[], wv[0][0]+2:[], wv[0][0]+3:[]}
    for i in range(N):
        w, v = wv[i]
        dic[w].append(v)
    
    wv = list(dic.items())
    tmp = [None] * 4
    for i in range(4):
        num, l = wv[i]
        l = sorted(l, reverse=True)
        for j in range(1, len(l)):
            l[j] += l[j-1]
        tmp[i] = [0] + l

    ans = 0
    for i in range(len(tmp[0])):
        now_w = base_w * i
        if now_w > W:
            break
        for j in range(len(tmp[1])):
            now_w += (base_w + 1) * j
            if now_w > W:
                break
            for k in range(len(tmp[2])):
                now_w += (base_w + 2) * k
                if now_w > W:
                    break
                for l in range(len(tmp[3])):
                    now_w += (base_w + 3) * l
                    if now_w > W:
                        break
                    else:
                        val = tmp[0][i] + tmp[1][j] + tmp[2][k] + tmp[3][l]
                        if ans < val:
                            ans = val
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections
def main():

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

    for w in goods:
        goods[w].sort(reverse = True)

    cur = dict()
    cur[0] = 0
    for w in goods:
        temp = cur.copy()
        for w1 in temp:
            w2, v2 = w1, cur[w1]
            for i in range(len(goods[w])):
                w2 += w
                v2 += goods[w][i]
                if w2 <= W:
                    if w2 not in cur:
                        cur[w2] = v2
                    else:
                        cur[w2] = max(cur[w2], v2)
    max_v = 0
    for w in cur:
        max_v = max(max_v, cur[w])
    return max_v

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

def chk(samp):
    for i in samp:
        print(samp)

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]

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



#価値毎に置き換える
wl = [[] for i in range(4)]

#価値ごとのりすとに入れていく
for i in range(N):
    wl[w[0]-w[i]].append(v[i])


#ソートして最初に0を追加する。0は選択しない場合
for i in range(4):
    wl[i].sort(reverse = 1)
    wl[i].insert(0,0)
    

#累積和を作る
for i in range(4):
    wl[i] = list(accumulate(wl[i]))
    
#出力用変数
out = 0


for i,wl0 in enumerate(wl[0]):
   for j,wl1 in enumerate(wl[1]):
       for k,wl2 in enumerate(wl[2]):
           for l,wl3 in enumerate(wl[3]):
               if i*(w[0])+j*(w[0]+1)+k*(w[0]+2)+l*(w[0]+3) > W:
                   continue
               else:
                   out = max(out,wl0+wl1+wl2+wl3)
                   
print(out)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

def chk(samp):
    for i in samp:
        print(samp)

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]

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



#価値毎に置き換える
wl = [[] for i in range(4)]

#価値ごとのりすとに入れていく
for i in range(N):
    wl[w[0]-w[i]].append(v[i])


#ソートして最初に0を追加する。0は選択しない場合
for i in range(4):
    wl[i].sort(reverse = 1)
    wl[i].insert(0,0)
    

#累積和を作る
for i in range(4):
    wl[i] = list(accumulate(wl[i]))
    
#出力用変数
out = 0


for i,wl0 in enumerate(wl[0]):
   for j,wl1 in enumerate(wl[1]):
       for k,wl2 in enumerate(wl[2]):
           for l,wl3 in enumerate(wl[3]):
               if i*(w[0])+j*(w[1])+k*(w[2])+l*(w[3]) > W:
                   continue
               else:
                   out = max(out,wl0+wl1+wl2+wl3)
                   
print(out)

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 + 1) * n + 1)
    dp[0] = 0
    minw =  wv[0][0]
    if minw <= 3 * n:
        for w, v in wv:
            for i in range((3 * n + 1) * 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(W // minw, 0, -1):
                for k in range(min(W % minw, 3 * n + 1), w - 1, -1):
                    dp[(3 * n + 1) * i + k] = max(dp[(3 * n + 1) * (i - 1) + k - w] + v, dp[(3 * n + 1) * i + k])
        print(max(dp[:W // minw * (3 * n + 1) + 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 + 1) * n + 1)
    dp[0] = 0
    minw =  wv[0][0]
    if minw <= 3 * n:
        for w, v in wv:
            for i in range((3 * n + 1) * 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(W // minw, 0, -1):
                for k in range(3 * n + 1, w - 1, -1):
                    dp[(3 * n + 1) * i + k] = max(dp[(3 * n + 1) * (i - 1) + k - w] + v, dp[(3 * n + 1) * i + k])
        print(max(dp[:W // minw * (3 * n + 1) + 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 + 1) * n + 1)
    dp[0] = 0
    minw =  wv[0][0]
    if minw <= 3 * n:
        for w, v in wv:
            for i in range((3 * n + 1) * 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 + 1, w - 1, -1):
                    dp[(3 * n + 1) * i + k] = max(dp[(3 * n + 1) * (i - 1) + k - w] + v, dp[(3 * n + 1) * i + k])
        print(max(dp[:W // minw * (3 * n + 1) + 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 + 1) * n + 1)
    dp[0] = 0
    minw =  wv[0][0]
    if minw <= 3 * n:
        for w, v in wv:
            for i in range((3 * n + 1) * 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 + 1, w - 1, -1):
                    dp[(3 * n + 1) * i + k] = max(dp[(3 * n + 1) * (i - 1) + k] + v, dp[(3 * n + 1) * i + k])
        print(max(dp[:W // minw * (3 * n + 1) + 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 + 1) * n + 1)
    dp[0] = 0
    minw =  wv[0][0]
    if minw <= 3 * n:
        for w, v in wv:
            for i in range((3 * n + 1) * 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 + 1, w - 1, -1):
                    dp[(3 * n + 1) * i + k] = max(dp[(3 * n + 1) * (i - 1) + k] + v, dp[(3 * n + 1) * i + k])
        print(max(dp[:W // minw * 4 * 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] * (4 * n * n + 1)
    dp[0] = 0
    minw =  wv[0][0]
    if minw <= 4 * n:
        for w, v in wv:
            for i in range(4 * 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(4 * n, w - 1, -1):
                    dp[i * 4 * n + k] = max(dp[(i - 1) * 4 * n + k - w] + v, dp[i * 4 * n + k])
        print(max(dp[:W // minw * 4 * 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] * (4 * n * n + 1)
    dp[0] = 0
    minw =  wv[0][0]
    if minw < 4 * n:
        for w, v in wv:
            for i in range(4 * 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(4 * n, w - 1, -1):
                    dp[i * 4 * n + k] = max(dp[(i - 1) * 4 * n + k - w] + v, dp[i * 4 * n + k])
        print(max(dp[:W // minw * 4 * n + W % minw + 1]))
    return

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