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:
# coding: utf-8
# Your code here!
N,W=map(int,input().split())
dp=[[-1]*301 for i in range(N+1)]
dp[0][0]=0

for i in range(N):
    w,v=map(int,input().split())
    if i==0:
        base=w
    for i in range(N)[::-1]:
        for j in range(301)[::-1]:
            if dp[i][j]!=-1:
                dp[i+1][j+w-base]=max(dp[i][j]+v,dp[i+1][j+w-base])

ans=0
for index,item in enumerate(dp):
    if W-index*base<=0:
        break
    ans=max(max(item[:W-index*base+1]),ans)
    #print(item[:W-index*base+1])

print(ans)

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
wv=[]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    wv.append([a,b])
    v.append(b)
v.sort(reverse=True)
ans=0
w0=wv[0][0]
wp=3*n+1
dp=[[-1 for jjj in range(n+1)] for iii in range(3*n+1)]
dp[0][0]=0
for i in range(n):
    for jj in range(n):
        for k in range(wp-1,-1,-1):
            if dp[k][jj]>=0 and k+wv[i][0]-w0<=wp:
                dp[k+wv[i][0]-w0][jj+1]=max(dp[k][jj]+wv[i][1],dp[k+wv[i][0]-w0][jj+1])
for i in range(1,n+1):
    wp=w-w0*i
    if wp<0:
        continue
    elif wp>=3*i:
        ans=max(ans,sum(v[:i]))
    else:
        for j in range(i+1):
            for k in range(wp+1):
                ans=max(dp[k][j],ans)
print(ans)

Submission status: Wrong Answer

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

V0 = []
V1 = []
V2 = []
V3 = []

for i in range(N):
    w, v = map(int, input().split())
    if i == 0:
        w1 = w
        V0.append(v)
    else:
        if w == w1:
            V0.append(v)
        elif w == w1+1:
            V1.append(v)
        elif w == w1+2:
            V2.append(v)
        else:
            V3.append(v)

V0.sort(reverse=True)
V1.sort(reverse=True)
V2.sort(reverse=True)
V3.sort(reverse=True)

from itertools import accumulate
CV0 = [0] + V0
CV0 = list(accumulate(CV0))
CV1 = [0] + V1
CV1 = list(accumulate(CV1))
CV2 = [0] + V2
CV2 = list(accumulate(CV2))
CV3 = [0] + V3
CV3 = list(accumulate(CV3))

print(CV0)
print(CV1)
print(CV2)
print(CV3)

ans = -float('inf')
for a in range(len(V0)+1):
    for b in range(len(V1)+1):
        for c in range(len(V2)+1):
            for d in range(len(V3)+1):
                if w1*a + (w1+1)*b + (w1+2)*c + (w1+3)*d <= W:
                    sum_v = CV0[a]+CV1[b]+CV2[c]+CV3[d]
                    ans = max(ans, sum_v)

print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
d = {i: [] for i in range(0, 4)}

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

for i in range(4):
    d[i].sort()


def isOK(x, y, z):
    return w1 * N + 3 * x + 2 * y + z <= W


ans = 0
for i in range(len(d[0]) + 1):
    v0 = sum(d[0][:i])
    w0 = weight * i
    if w0 > W:
        break
    for j in range(len(d[1]) + 1):
        v1 = v0 + sum(d[1][:j])
        w1 = (weight + 1) * j
        if w0 + w1 > W:
            break
        for k in range(len(d[2]) + 1):
            v2 = v1 + sum(d[2][:k])
            w2 = (weight + 2) * k
            if w0 + w1 + w2 > W:
                break

            rest = W - (w0 + w1 + w2)
            num = min(len(d[3]), rest // (weight + 3))
            value = v2 + sum(d[3][:num])
            ans = max(ans, value)

print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
d = {i: [] for i in range(0, 4)}

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

for i in range(4):
    d[i].sort()


def isOK(x, y, z):
    return w1 * N + 3 * x + 2 * y + z <= W


ans = 0
for i in range(len(d[0]) + 1):
    v0 = sum(d[0][:i])
    w0 = weight * i
    if w0 > W:
        break
    for j in range(len(d[1]) + 1):
        v1 = v0 + sum(d[1][:j])
        w1 = (weight + 1) * j
        if w0 + w1 > W:
            break
        for k in range(len(d[2]) + 1):
            v2 = v1 + sum(d[2][:k])
            w2 = (weight + 2) * k
            if w0 + w1 + w2 > W:
                break

            rest = W - (w0 - +w1 + w2)
            num = min(len(d[3]), rest // (weight + 3))
            value = v2 + sum(d[3][:num])
            ans = max(ans, value)

print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    N,W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]
    base_weight = wv[0][0]
    
    if base_weight > W:
        print(0)
        return
    
    wv_ = [[wv[i][0]-base_weight, wv[i][1]] for i in range(N)]
    dp_W = min(3*N,W-base_weight)
    dp_table = [[0]*(dp_W+1) for _ in range(N+1)]
    # dp[i][j] := i番目の品物を使ってw[0]+jの重さ以下の価値最大化テーブル
    
    for i in range(0,N):
        for j in range(0,dp_W+1):
            if j >= wv_[i][0] and j < wv[i][0]:
                # 足されてない場合
                if dp_table[i][j-wv_[i][0]] == 0:
                    dp_table[i+1][j] = max(dp_table[i][j], dp_table[i][j-wv_[i][0]]+wv_[i][1])
                else:
                    dp_table[i+1][j] = max(dp_table[i][j], wv_[i][1])
                    
            elif j >= wv[i][0]:
                dp_table[i+1][j] = max(dp_table[i][j], dp_table[i][j-wv[i][0]]+wv[i][1])
            else:
                # ここも切り取った部分考えないといけない
                dp_table[i+1][j] = dp_table[i][j]
            
                
    # print(dp_table)
    print(dp_table[N][dp_W])
    
solve()

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])
#print(wv)
w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    if wv[i][0]==w0:
        k=wv[i][1]+x[0][-1]
        l=len(x[0])
        if l*w0<=w:x[0].append(k)
    elif wv[i][0]==w0+1:
        k=wv[i][1]+x[1][-1]
        l=len(x[1])
        if l*(w0+1)<=w:x[1].append(k)
    elif wv[i][0]==w0+2:
        k=wv[i][1]+x[2][-1]
        l=len(x[2])
        if l*(w0+2)<=w:x[2].append(k)
    else:
        k=wv[i][1]+x[3][-1]
        l=len(x[3])
        if l*(w0+3)<=w:x[3].append(k)
#print(x)
ma=0
for i in range(len(x[0])):
    for j in range(len(x[1])):
        for k in range(len(x[2])):
            for l in range(len(x[3])):
                if i*w0+j*(w0+1)+k*(w0+2)+l*(w0+3)<=w:
                    ma_sub=0
                    ma_sub+=x[0][i]
                    ma_sub+=x[1][j]
                    ma_sub+=x[2][k]
                    ma_sub+=x[3][l]
                    ma=max(ma,ma_sub)
                    break
print(ma)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def main():
    n,W = inpm()
    v = [[] for _ in range(4)]
    w0 = 0
    for i in range(n):
        wv = inpl()
        if i == 0:
            w0 = wv[0]
        v[ wv[0]-w0 ].append(wv[1])
    for i in range(4):
        v[i] = sorted(v[i])
        vv = [0 for _ in range(len(v[i])+1)]
        for j in range(len(v[i])):
            vv[j+1] = vv[j] + v[i][j]
        v[i] = vv
    ans = 0
    for n1 in range(len(v[0])):
        for n2 in range(len(v[1])):
            for n3 in range(len(v[2])):
                for n4 in range(len(v[3])):
                    if W < w0*(n1+n2+n3+n4) + n2 + n3*2 + n4*3:
                        continue
                    ans = max(ans,v[0][n1]+v[1][n2]+v[2][n3]+v[3][n4])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def Knapsack1(w0,W,w,v): # n個の品物(重さw[i],価値v[i]) 総重量W以内での価値の最大化 計算量O(W*N)
    n=len(w)
    # dp[i][j] : i番目の品物で重さj以下の価値の最大値
    dp=[[0 for _ in range(3*n+1)] for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(3*n+1):
            dp[i][j]=max( dp[i][j],dp[i-1][j] )
            if j >= w[i-1]+w0:
                dp[i][j]=max(dp[i][j],dp[i-1][j-w[i-1]-w0]+v[i-1])
    print(max(dp[n]))


def main():
    n,W = inpm()
    w = []
    v = []
    w0 = 0
    for i in range(n):
        wv = inpl()
        if i == 0:
            w0 = wv[0]
        w.append(wv[0]-w0)
        v.append(wv[1])
    Knapsack1(w0,W,w,v)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def Knapsack2(W,w,v): # n個の品物(重さw[i],価値v[i]) 価値iを達成する重量の最小化 計算量O(V*N)
    n=len(w)
    v_max=10**5+5
    # dp[i] : 価値iの組み合わせを達成する重量の最小値
    dp=[0]+[float('inf') for _ in range(v_max+1)]
    for i in range(n):
        for j in range(v_max,v[i]-1,-1):
            if j >= v[i]:
                dp[j]=min(dp[j],dp[j-v[i]]+w[i])
    ans=0
    for i in range(v_max+1):
        if dp[i]<=W:
            ans=i
    print(ans)

def main():
    n,W = inpm()
    w = []
    v = []
    for _ in range(n):
        wv = inpl()
        w.append(wv[0])
        v.append(wv[1])
    Knapsack2(W,w,v)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split(' '))
A = [list(map(int, input().split(' '))) for i in range(N)]
if A[0][0] > 300:
    if W//A[0][0] > 100:
        print(sum(list(zip(*A))[1]))
        exit()
    if W%A[0][0] >= 300:
        W = W//A[0][0]*300+300
    else:
        W = W//A[0][0]*300+W%A[0][0]
    k = A[0][0]
    for i in range(N):
        A[i][0] = 300+A[i][0]-k

DP = [[0 for i in range(31000)] for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,31000):
        DP[i][j] = max(DP[i][j],DP[i-1][j],DP[i][j-1])
        if j-A[i-1][0]>=0:
            DP[i][j] = max(DP[i][j],DP[i-1][j-A[i-1][0]]+A[i-1][1])            

print(DP[N][W])

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split(' '))
A = [list(map(int, input().split(' '))) for i in range(N)]
if A[0][0] > 300:
    if W//A[0][0] > 100:
        print(sum(list(zip(*A))[1]))
        exit()
    if W%A[0][0] > 300:
        W = W//A[0][0]*300+300
    else:
        W = W//A[0][0]*300+W%A[0][0]
    k = A[0][0]
    for i in range(N):
        A[i][0] = 300+A[i][0]-k

DP = [[0 for i in range(31000)] for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,31000):
        DP[i][j] = max(DP[i][j],DP[i-1][j],DP[i][j-1])
        if j-A[i-1][0]>=0:
            DP[i][j] = max(DP[i][j],DP[i-1][j-A[i-1][0]]+A[i-1][1])            

print(DP[N][W])

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split(' '))
A = [list(map(int, input().split(' '))) for i in range(N)]
if A[0][0] > 300:
    if W%A[0][0] > 300:
        W = W//A[0][0]*300+300
    else:
        W = W//A[0][0]*300+W%A[0][0]
    k = A[0][0]
    for i in range(N):
        A[i][0] = 300+A[i][0]-k

DP = [[0 for i in range(31000)] for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,31000):
        DP[i][j] = max(DP[i][j],DP[i-1][j],DP[i][j-1])
        if j-A[i-1][0]>=0:
            DP[i][j] = max(DP[i][j],DP[i-1][j-A[i-1][0]]+A[i-1][1])
Sum = 0
for i in range(N):
    Sum += A[i][0]
print(DP[N][min(W,Sum)])

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split(' '))
A = [list(map(int, input().split(' '))) for i in range(N)]
if A[0][0] > 300:
    if W%A[0][0] > 300:
        W = W//A[0][0]*300+300
    else:
        W = W//A[0][0]*300+W%A[0][0]
    k = A[0][0]
    for i in range(N):
        A[i][0] = 300+A[i][0]-k

DP = [[0 for i in range(31000)] for i in range(N+1)]
for j in range(1,31000):
    for i in range(1,N+1):   
        DP[i][j] = max(DP[i][j],DP[i-1][j],DP[i][j-1])
        if j-A[i-1][0]>=0:
            DP[i][j] = max(DP[i][j],DP[i-1][j-A[i-1][0]]+A[i-1][1])
print(DP[N][W])

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split(' '))
A = [list(map(int, input().split(' '))) for i in range(N)]
if A[0][0] > 300:
    if W%A[0][0] > 300:
        W = W//A[0][0]*300+300
    else:
        W = W//A[0][0]*300+W%A[0][0]
    k = A[0][0]
    for i in range(N):
        A[i][0] = 300+A[i][0]-k

DP = [[0 for i in range(31000)] for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,31000):
        DP[i][j] = max(DP[i][j],DP[i-1][j],DP[i][j-1])
        if j-A[i-1][0]>=0:
            DP[i][j] = max(DP[i][j],DP[i-1][j-A[i-1][0]]+A[i-1][1])
print(DP[N][W])

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate, product
from operator import itemgetter
read = sys.stdin.read

N, W, *wv = map(int, read().split())
w1 = wv[0]
V = [[0] for _ in range(4)]

for w, v in sorted(zip(*[iter(wv)] * 2), key=itemgetter(1)):
    V[w - w1].append(v)


V = list(map(list, map(accumulate, V)))
n = [len(V[i]) for i in range(4)]
answer = 0
for a, b, c, d in product(range(n[0]), range(n[1]), range(n[2]), range(n[3])):
    if b + c * 2 + d * 3 + (a + b + c + d) * w1 > W:
        continue

    v = V[0][a] + V[1][b] + V[2][c] + V[3][d]
    if v > answer:
        answer = v

print(answer)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w0, v0 = map(int, input().split())
X = [[] for _ in range(4)]
X[0].append(v0)
for _ in range(N-1):
    w, v = map(int, input().split())
    X[w-w0].append(v)

X = [[0] + sorted(x)[::-1] for x in X]
for i in range(3):
    for j in range(1, len(X[i])):
        X[i][j] += X[i][j-1]
ma = 0
for i in range(N+1):
    for j in range(N+1-i):
        for k in range(N+1-i-j):
            l = min(N-i-j-k, (W - (w0 * i + (w0+1) * j + (w0+2) * k)) // (w0+3))
            if l < 0: continue
            if i < len(X[0]) and j < len(X[1]) and k < len(X[2]) and l < len(X[3]):
                ma = max(ma, X[0][i] + X[1][j] + X[2][k] + X[3][l])
print(ma)

Submission status: Wrong Answer

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

a = wv[0][0]
d = []
for i in range(n + 1):
    _d = []
    for ii in range(n + 1):
        __d = []
        for j in range(4):
            __d.append(0)
        _d.append(__d)
    d.append(_d)


# i=0
d[0][0][0] = 0

for i in range(1, n + 1):
    for ii in range(n + 1):
        for j in range(4):
            # print(i, j)
            # a * ii, (a + 3) * ii + 1
            if j + a ** ii < wv[i - 1][0]:
                tmp = 0
                d[i][ii][j] = d[i-1][ii][j]

            else:
                tmp = d[i-1][ii][j]
                if j + a ** ii - wv[i-1][0] >= 0:
                    x = j + a ** ii - wv[i-1][0]

                    cands = []
                    for jj in range(4):
                        if (x - jj) % a == 0 and (x - jj) // a < len(d[i-1]):
                            cands.append([(x - jj) // a, jj])
                    cands = sorted(cands)
                    if cands:
                        cand = cands[-1]

                        tmp = max(tmp, d[i-1][cand[0]][cand[1]] + wv[i-1][1])

                d[i][ii][j] = tmp

ans = 0
for i in range(n + 1):
    for ii in range(i + 1):
        for j in range(4):
            w = a ** ii + j
            if w <= W:
                ans = max(ans, d[i][ii][j])
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

num = [0]*4
w0 = L[0][0]
for i in range(N):
    num[L[i][0]-w0] += 1
    
L.sort(reverse=True, key=itemgetter(1))
L.sort()
prev = w0
for i in range(1, N):
    if L[i][0] == prev:
        L[i][1] += L[i-1][1]
    else:
        prev += 1
        
ans = 0
for i in range(-1, num[0], 1):
    if i < 0:
        ci = 0
        wi = 0
    else:
        ci = L[i][1]
        wi = (i+1)*w0
        if wi > W:
            continue
    for j in range(-1, num[1], 1):
        wj = (j+1)*(w0+1)
        cj = 0
        if j >= 0:
            if wi+wj > W:
                continue
            cj += L[j+num[0]][1]
        for k in range(-1, num[2], 1):
            wk = (k+1)*(w0+2)
            ck = 0
            if k >= 0:
                if wi+wj+wk > W:
                    continue
                ck += L[k+num[0]+num[1]][1]
            for l in range(-1, num[3], 1):
                wl = (l+1)*(w0+3)
                cl = 0
                if l >= 0:
                    if wi+wj+wk+wl > W:
                        continue
                    cl += L[l+num[0]+num[1]+num[2]][1]
                ans = max(ans, ci+cj+ck+cl)
            
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

num = [0]*4
w0 = L[0][0]
for i in range(N):
    num[L[i][0]-w0] += 1
    
L.sort(reverse=True, key=itemgetter(1))
L.sort()
prev = w0
for i in range(1, N):
    if L[i][0] == prev:
        L[i][1] += L[i-1][1]
    else:
        prev += 1
        
ans = 0
for i in range(-1, num[0], 1):
    if i < 0:
        ci = 0
        wi = 0
    else:
        ci = L[i][1]
        wi = (i+1)*w0
        if wi > W:
            continue
    for j in range(-1, num[1], 1):
        wj = (j+1)*(w0+1)
        cj = 0
        if j >= 0:
            if wi+wj > W:
                break
            cj += L[j+num[0]][1]
        for k in range(-1, num[2], 1):
            wk = (k+1)*(w0+2)
            ck = 0
            if k >= 0:
                if wi+wj+wk > W:
                    break
                ck += L[k+num[0]+num[1]][1]
            c = ci+cj+ck
            l = (W-wi-wj-wk)//(w0+3)
            if l > 0 and num[3] > 0:
                l = min(l, num[3])
                if wi+wj+wk+l*(w0+3) <= W:
                    c += L[l-1+num[0]+num[1]+num[2]][1]
            ans = max(ans, c)
            
print(ans)

Submission status: Wrong Answer

Solution code:
#w1<=wi<w1+3
from itertools import product
n,w_max = map(int, input().split( ))
w = {}
w1,v1 = map(int, input().split( ))
w[w1] = [v1]
w2 = w1+1
w3 =w2+1
w4 = w3+1
w[w2] = [0]
w[w3] = [0]
w[w4] = [0]
for i in range(n-1):
    wi,vi=map(int, input().split( ))
    w[wi].append(vi)

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

ans = 0
l1 = len(w[w1])+1
l2 = len(w[w2])+1
l3 = len(w[w3])+1
l4 = len(w[w4])+1
for i1,i2,i3,i4 in product(range(l1),range(l2),range(l3),range(l4)):
    if w1*i1+w2*i2+w3*i3+w4*i4<=w_max:
        ans = max(ans,sum(w[w1][:i1])+sum(w[w2][:i2])+sum(w[w3][:i3])+sum(w[w4][:w4]))

print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
items = []
for _ in range(N):
  w,v = map(int,input().split())
  if w > W:
    continue
  else:
    items.append([v/w, -w, v])
items.sort(reverse=True)

ans = 0
len_items = len(items)
for i in range(len_items):
  tmp_ans = 0
  sumw = 0
  for unit_v, w, v in items[i:] + items[:i]:
    w *= -1
    if sumw + w <= W:
      sumw += w
      tmp_ans += v
    else:
      continue
  ans = max(ans, tmp_ans)
print(ans)
#print(items)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
items = []
for _ in range(N):
  w,v = map(int,input().split())
  if w > W:
    continue
  else:
    items.append([v/w, -w, v])
items.sort(reverse=True)

ans = 0
len_items = len(items)
for i in range(len_items):
  tmp_ans = 0
  sumw = 0
  for unit_v, w, v in items[i:]:
    w *= -1
    if sumw + w <= W:
      sumw += w
      tmp_ans += v
    else:
      continue
  ans = max(ans, tmp_ans)
print(ans)
#print(items)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
items = []
for _ in range(N):
  w,v = map(int,input().split())
  if w > W:
    continue
  else:
    items.append([v/w, w, v])
items.sort(reverse=True)

ans = 0
len_items = len(items)
for i in range(len_items):
  tmp_ans = 0
  sumw = 0
  for unit_v, w, v in items[i:]:
    if sumw + w <= W:
      sumw += w
      tmp_ans += v
    else:
      continue
  ans = max(ans, tmp_ans)
print(ans)
#print(items)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
items = []
for _ in range(N):
  w,v = map(int,input().split())
  if w > W:
    continue
  else:
    items.append([v/w, w, v])
items.sort(reverse=True)

sumw = 0
ans = 0
for unit_v, w, v in items:
  if sumw + w <= W:
    sumw += w
    ans += v
  else:
    continue
print(ans)

Submission status: Wrong Answer

Solution code:
# simple knapsack
n,W=map(int,input().split())
sacklist=[[]for i in range(4)]
w1,v1=map(int,input().split())
sacklist[0].append(v1)
for _ in range(n-1):
    w,v=map(int,input().split())
    sacklist[w-w1].append(v)
for k in sacklist:
    k=sorted(k,reverse=True)
len1=len(sacklist[0])
len2=len(sacklist[1])
len3=len(sacklist[2])
len4=len(sacklist[3])
sumlist1=[]
sumlist2=[]
sumlist3=[]
sumlist4=[]
for _ in range(len1+1):
    sumlist1.append(sum(sacklist[0][:_]))
for _ in range(len2+1):
    sumlist2.append(sum(sacklist[1][:_]))
for _ in range(len3+1):
    sumlist3.append(sum(sacklist[2][:_]))
for _ in range(len4+1):
    sumlist4.append(sum(sacklist[3][:_]))
l1=len(sumlist1)
l2=len(sumlist2)
l3=len(sumlist3)
l4=len(sumlist4)
answer=[]
for i in range(l1):
    for j in range(l2):
        for k in range(l3):
            for m in range(l4):
                if ((w1)*i+(w1+1)*j+(w1+2)*k+(w1+3)*m)<= W:
                    answer.append(sumlist1[i]+sumlist2[j]+sumlist3[k]+sumlist4[m])
print(max(answer))

Submission status: Wrong Answer

Solution code:
# simple knapsack
n,W=map(int,input().split())
sacklist=[[]for i in range(4)]
w,v=map(int,input().split())
ws=w
sacklist[0].append(v)
for _ in range(n-1):
    w,v=map(int,input().split())
    sacklist[w-ws].append(v)
for k in sacklist:
    k=sorted(k,reverse=True)
len1=len(sacklist[0])
len2=len(sacklist[1])
len3=len(sacklist[2])
len4=len(sacklist[3])
sumlist1=[]
sumlist2=[]
sumlist3=[]
sumlist4=[]
for _ in range(len1+1):
    sumlist1.append(sum(sacklist[0][:_]))
for _ in range(len2+1):
    sumlist2.append(sum(sacklist[1][:_]))
for _ in range(len3+1):
    sumlist3.append(sum(sacklist[2][:_]))
for _ in range(len4+1):
    sumlist4.append(sum(sacklist[3][:_]))
l1=len(sumlist1)
l2=len(sumlist2)
l3=len(sumlist3)
l4=len(sumlist4)
answer=[]
for i in range(l1):
    for j in range(l2):
        for k in range(l3):
            for m in range(l4):
                if (ws)*i+(ws+1)*j+(ws+2)*k+(ws+3)*m<=W:
                    answer.append(sumlist1[i]+sumlist2[j]+sumlist3[k]+sumlist4[m])
print(max(answer))

Submission status: Wrong Answer

Solution code:
# simple knapsack
n,W=map(int,input().split())
sacklist=[[]for i in range(4)]
w,v=map(int,input().split())
ws=w
sacklist[0].append(v)
for i in range(n-1):
    w,v=map(int,input().split())
    sacklist[w-ws].append(v)
for k in sacklist:
    k=sorted(k,reverse=True)
len1=len(sacklist[0])
len2=len(sacklist[1])
len3=len(sacklist[2])
len4=len(sacklist[3])
sumlist1=[0]
sumlist2=[0]
sumlist3=[0]
sumlist4=[0]
for i in range(len1):
    sumlist1.append(sumlist1[-1]+sacklist[0][i])
for j in range(len2):
    sumlist2.append(sumlist2[-1]+sacklist[1][j])
for k in range(len3):
    sumlist3.append(sumlist3[-1]+sacklist[2][k])
for i in range(len4):
    sumlist4.append(sumlist4[-1]+sacklist[3][i])
l1=len(sumlist1)
l2=len(sumlist2)
l3=len(sumlist3)
l4=len(sumlist4)
answer=[]
for i in range(l1):
    for j in range(l2):
        for k in range(l3):
            for m in range(l4):
                if (ws)*i+(ws+1)*j+(ws+2)*k+(ws+3)*m<=W:
                    answer.append(sumlist1[i]+sumlist2[j]+sumlist3[k]+sumlist4[m])
print(max(answer))

Submission status: Wrong Answer

Solution code:
# simple knapsack
n,W=map(int,input().split())
sacklist=[[]for i in range(4)]
w,v=map(int,input().split())
ws=w
sacklist[0].append(v)
for i in range(n-1):
    w,v=map(int,input().split())
    sacklist[w-ws].append(v)
for k in sacklist:
    k=sorted(k,reverse=True)
len1=len(sacklist[0])
len2=len(sacklist[1])
len3=len(sacklist[2])
len4=len(sacklist[3])
sumlist1=[0]
sumlist2=[0]
sumlist3=[0]
sumlist4=[0]
for i in range(len1):
    sumlist1.append(sumlist1[-1]+sacklist[0][i])
for j in range(len2):
    sumlist2.append(sumlist2[-1]+sacklist[1][j])
for k in range(len3):
    sumlist3.append(sumlist3[-1]+sacklist[2][k])
for i in range(len4):
    sumlist4.append(sumlist4[-1]+sacklist[3][i])
l1=len(sumlist1)
l2=len(sumlist2)
l3=len(sumlist3)
l4=len(sumlist4)
answer=0
for i in range(l1):
    for j in range(l2):
        for k in range(l3):
            for m in range(l4):
                if (ws)*i+(ws+1)*j+(ws+2)*k+(ws+3)*m<=W:
                    answer=max(answer,sumlist1[i]+sumlist2[j]+sumlist3[k]+sumlist4[m])
print(answer)

Submission status: Wrong Answer

Solution code:
#simple knapsack
n,W=map(int,input().split())
sacklist=[[]for i in range(4)]
w,v=map(int,input().split())
w_0=w
sacklist[0].append(v)
for i in range(n-1):
    w,v=map(int,input().split())
    sacklist[w-w_0].append(v)
for k in sacklist:
    k=sorted(k)
len1=len(sacklist[0])
len2=len(sacklist[1])
len3=len(sacklist[2])
len4=len(sacklist[3])
sumlist1=[0]
sumlist2=[0]
sumlist3=[0]
sumlist4=[0]
for i in range(len1):
    sumlist1.append(sumlist1[-1]+sacklist[0][i])
for j in range(len2):
    sumlist2.append(sumlist2[-1]+sacklist[1][j])
for k in range(len3):
    sumlist3.append(sumlist3[-1]+sacklist[2][k])
for i in range(len4):
    sumlist4.append(sumlist4[-1]+sacklist[3][i])
l1=len(sumlist1)
l2=len(sumlist2)
l3=len(sumlist3)
l4=len(sumlist4)
#[0, 1]価値はw_0
#[0, 4, 8]価値はw_0+1
#[0, 10]価値はw_0+2
#[0]価値はw_0+3
answer=0
for i in range(l1):
    for j in range(l2):
        for k in range(l3):
            for m in range(l4):
                if w_0*i+(w_0+1)*j+(w_0+2)*k+(w_0+3)*m<=W:
                    answer=max(answer,sumlist1[i]+sumlist2[j]+sumlist3[k]+sumlist4[m])
print(answer)

Submission status: Wrong Answer

Solution code:
n, W = [int(x) for x in input().split()]
wv = [[int(x) for x in input().split()] for _ in range(n)] # weight, value

min_w = wv[0][0]

for i in range(n):
    wv[i].insert(0, wv[i][1] / wv[i][0])
wv.sort(reverse=1)  # sort in order that high value per unit weight.

sw = [0] * n   # camulative sum of weights
sw[0] = wv[0][1]
sv = [0] * n   # camulative sum of values
sv[0] = wv[0][2]  
for i in range(n-1):
    sw[i+1] = sw[i] + wv[i+1][1] 
    sv[i+1] = sv[i] + wv[i+1][2]

ans = 0
for i in range(n):
    if sw[i] < W:
        ans = sv[i] # continuous updating
        continue
    elif sw[i] == W:
        ans = sv[i]
        break
    else:
        if i > 0:
            d = W - sw[i-1]
            for j in range(d, min_w-1, -1):  # if d >= min_w
                for k in range(i+1, n):
                    if j == wv[k][1]:
                        ans += wv[k][2]
                        print(ans)
                        exit()
        else:
            for j in range(W, min_w-1, -1):
                for k in range(1, n):
                    if j == wv[k][1]:
                        ans += wv[k][2]
                        print(ans)
                        exit()
        

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())
V=[[0] for _ in [0]*4]
for i in range(N):V[w[i]-w[0]].append(v[i])
for i in range(4):
    V[i].sort()
    for j in range(len(V[i])-1):V[i][j+1]+=V[i][j]

a=0
for i in range(len(V[0])):
    for j in range(len(V[1])):
            for k in range(len(V[2])):
                for l in range(len(V[3])):
                    if i*w[0]+j*-~w[0]+k*-~-~w[0]+l*-~-~-~w[0]<=W:a=max(a,V[0][i]+V[1][j]+V[2][k]+V[3][l])
print(a)

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
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)