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:
def SimpleKnapsack():
    n, w = map(int, input().split())
    INF = float('inf')
    num = 10**7
    
    # DP配列
    # dp[i]:バッグの合計価値がiのときの最小の重さ
    dp = [INF for _ in range(num+1)]

    # DP初期値代入
    dp[0] = 0
    
    # DP
    for _ in range(n):
        a, b = map(int, input().split())
        for i in range(num, b-1, -1):
            dp[i] = min(dp[i], dp[i-b]+a)
    for i in range(num, -1, -1):
        if dp[i] <= w:
            print(i)
            break
    
if __name__ == '__main__':
    SimpleKnapsack()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, W, WV):
    vl = {}
    vl[WV[0][0]] = list()
    vl[WV[0][0]+1] = list()
    vl[WV[0][0]+2] = list()
    vl[WV[0][0]+3] = list()
    for w, v in WV:
        vl[w].append(v)

    for v in vl.values():
        v.sort(reverse=True)
        v.insert(0, 0)


    wi, wj, wk, wl = vl.keys()
    ans = 0
    vis = 0
    for i, vi in enumerate(vl[wi]):
        if wi * i > W:
            break
        vis += vi
        vjs = 0
        for j, vj in enumerate(vl[wj]):
            if wi * i + wj * j > W:
                break
            vjs += vj
            vks = 0
            for k, vk in enumerate(vl[wk]):
                if wi*i + wj*j + wk*k> W:
                    break
                vks += vk
                ans = max(ans, vis+vjs+vks)
    return ans





def main():
    N, W = read_int_n()
    WV = [read_int_n() for _ in range(N)]
    print(slv(N, W, WV))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
wvs = []
for i in range(N):
    w,v = map(int, input().split())
    wvs.append((w,v))
# dp : n個入っていて、合計がwのときの最大値
w0 = wvs[0][0]
dp = [[[-1]*(330) for i in range(110)] for k in range(110)]
dp[0][0][0] = 0
for i in range(N):
    w, v = wvs[i]
    dw = w-w0
    for j in range(i+1):
        for k in range(301):
            # if k - dw >= 0:
            if dp[i][j][j] == -1:continue
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            dp[i+1][j+1][k+dw] = max(dp[i][j][k]+v, dp[i+1][j+1][k+dw])

d = dp[N]
ans = 0
for j in range(N+1):
    if W-j*w0 > 0:
        a = max(d[j][:W-j*w0+1])
        ans = max(ans, a)
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
wvs = []
for i in range(N):
    w,v = map(int, input().split())
    wvs.append((w,v))
# dp : n個入っていて、合計がwのときの最大値
w0 = wvs[0][0]
dp = [[[0]*(330) for i in range(110)] for k in range(110)]
for i in range(N):
    w, v = wvs[i]
    dw = w-w0
    for j in range(i+1):
        for k in range(301):
            # if k - dw >= 0:
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            dp[i+1][j+1][k+dw] = max(dp[i][j][k]+v, dp[i+1][j+1][k+dw])

d = dp[N]
ans = 0
for j in range(N+1):
    # print(dp[N][j][:W])
    if W-j*w0 > 0:
        a = max(d[j][:W-j*w0+1])
    else:
        a = 0
    ans = max(ans, a)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,w = list(map(int, input().split()))
wv = [None]*n
for i in range(n):
    wv[i] = tuple(map(int, input().split()))
w0 = wv[0][0]
wv = [(item[0]-w0, item[1]) for item in wv]
ans = 0
def sub(k):
    W = w - k*w0
    m = min(W, sum(item[0] for item in wv))
    dp = [[[0]*(k+1) for _ in range(m+1)] for _ in range(n+1)]
    for i in range(1,n+1):
        iw, iv = wv[i-1]
        for j in range(m+1):
            for kk in range(1,k+1):
                if j>=iw:
                    dp[i][j][kk] = max(dp[i-1][j][kk], dp[i-1][j-iw][kk-1]+iv)
                else:
                    dp[i][j][kk] = dp[i-1][j][kk]
#     print(k, dp)
    return max(dp[n][j][k] for j in range(m+1))
for k in range(1, w//w0):
    if k>n:
        break
    ans = max(ans, sub(k))
print(ans)

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n,ww=MI()
	w1,v1=MI()
	li=[[0] for _ in range(4)]
	li[0].append(v1)

	for _ in range(n-1):
		w,v=MI()
		li[w-w1].append(v)

	for i in range(4):
		li[i][1:].sort(reverse=True)
	#print(li)

	for i in range(4):
		for j in range(len(li[i])-1):
			li[i][j+1]+=li[i][j]
	#print(li)

	ans=0

	for i0 in range(len(li[0])):
		for i1 in range(len(li[1])):
			for i2 in range(len(li[2])):
				for i3 in range(len(li[3])):
					#print(i0,i1,i2,i3,li[0][i0],li[1][i1],li[2][i2],li[3][i3],w1*i0+(w1+1)*i1+(w1+2)*i2+(w1+3)*i3,li[0][i0]+li[1][i1]+li[2][i2]+li[3][i3],w,ans)
					if w1*i0+(w1+1)*i1+(w1+2)*i2+(w1+3)*i3<=ww:
						ans=max(ans,li[0][i0]+li[1][i1]+li[2][i2]+li[3][i3])

	print(ans)


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

n, W = (int(x) for x in input().split())
WV = [tuple(int(x) for x in input().split()) for _ in range(n)]
weight = [[] for _ in range(4)]  # weight[0] ~ weight[3]
w1 = WV[0][0]
for w, v in WV:
    weight[w - w1].append(v)

for wei in weight:
    wei.sort()

value_acc = [[] for _ in range(4)]
for i in range(4):
    value_acc[i] = list(accumulate(weight[i]))

ans = 0
for i in range(len(weight[0]) + 1):
    for j in range(len(weight[1]) + 1):
        for k in range(len(weight[2]) + 1):
            for l in range(len(weight[3]) + 1):
                tmp = w1 * i + (w1 + 1) * j + (w1 + 2) * k + (w1 + 3) * l
                if tmp <= W:
                    value = 0
                    for x, y in zip([0, 1, 2, 3], [i, j, k, l]):
                        if y - 1 >= 0:
                            value += value_acc[x][y - 1]
                    ans = max(ans, value)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,W = inpl()
a = [inpl() for _ in range(n)]
gds = [[0] for _ in range(4)]
a.sort()
a.sort(key = lambda x:x[1], reverse = True)
# print(a)
mi = a[0][0]
for i,(w,v) in enumerate(a):
    ind = w - mi
    gds[ind].append(v)
we = [i+mi for i in range(4)]
cnt = [0] * 4
for i in range(4):
    cnt[i] = len(gds[i])
    tmp = itertools.accumulate(gds[i])
    gds[i] = list(tmp)
# print(gds)
it = itertools.product(range(cnt[0]),range(cnt[1]),range(cnt[2]),range(cnt[3]))
res = 0
for ww in it:
    if sum(we[i]*ww[i] for i in range(4)) > W: continue
    now = sum(gds[i][ww[i]] for i in range(4))
    res = max(now, res)
print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,W = inpl()
a = [inpl() for _ in range(n)]
gds = [[0] for _ in range(4)]
a.sort()
mi = a[0][0]
for i,(w,v) in enumerate(a):
    ind = w - mi
    gds[ind].append(v)
we = [i+mi for i in range(4)]
cnt = [0] * 4
for i in range(4):
    gds[i].sort()
    cnt[i] = len(gds[i])
    tmp = itertools.accumulate(gds[i])
    gds[i] = list(tmp)
it = itertools.product(range(cnt[0]),range(cnt[1]),range(cnt[2]),range(cnt[3]))
res = 0
for ww in it:
    w0,w1,w2,w3 = ww
    if sum(we[i]*ww[i] for i in range(4)) > W: continue
    now = gds[0][w0] + gds[1][w1] + gds[2][w2] + gds[3][w3]
    res = max(now, res)
print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    from itertools import groupby, product
    base_w = w[0]
    v_list = [[] for _ in range(4)]
    for ww, vv in zip(w, v):
        v_list[ww-base_w].append(vv)
    v_list = [sorted(vv) for vv in v_list]
    acc_v = [[0] for _ in range(4)]
    for i, vv in enumerate(v_list):
        for vvv in vv:
            acc_v[i].append(acc_v[i][-1] + vvv)
    ans = 0
    for i, j, k, l in product(*[range(len(a)) for a in acc_v]):
        if i * base_w + j * (base_w + 1) + k * (base_w + 2)+ l * (base_w + 3) > W:
            continue
        ans = max(ans, acc_v[0][i] + acc_v[1][j] + acc_v[2][k] + acc_v[3][l])
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    print(solve(N, W, w, v))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    from itertools import product
    base_w = w[0]
    v_list = [[] for _ in range(4)]
    for ww, vv in zip(w, v):
        v_list[ww-base_w].append(vv)
    v_list = [sorted(vv) for vv in v_list]
    acc_v = [[0] * (N+1) for _ in range(4)]
    for i, vv in enumerate(v_list):
        for j, vvv in enumerate(vv):
            acc_v[i][j+1] = acc_v[i][j] + vvv
    return max(acc_v[0][i] + acc_v[1][j] + acc_v[2][k] + acc_v[3][l]
               for i, j, k, l in product(range(N+1), repeat=4)
               if i * base_w + j * (base_w + 1) + k * (base_w + 2)+ l * (base_w + 3) <= W)

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    print(solve(N, W, w, v))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    from itertools import product
    base_w = w[0]
    v_list = [[] for _ in range(4)]
    for ww, vv in zip(w, v):
        v_list[ww-base_w].append(vv)
    v_list = [sorted(vv) for vv in v_list]
    acc_v = [[0] * (N+1) for _ in range(4)]
    for i, vv in enumerate(v_list):
        for j, vvv in enumerate(vv):
            acc_v[i][j+1] = acc_v[i][j] + vvv
    ans = 0
    for i, j, k, l in product(range(N+1), repeat=4):
        if i * base_w + j * (base_w + 1) + k * (base_w + 2)+ l * (base_w + 3) > W:
            continue
        ans = max(ans, acc_v[0][i] + acc_v[1][j] + acc_v[2][k] + acc_v[3][l])
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    print(solve(N, W, w, v))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Wrong Answer

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

stuff = [[] for _ in range(4)]

w1,v1 = map(int,input().split())

stuff[0].append(v1)

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

for i in stuff:
    i.sort()

ans = 0
for a in range(len(stuff[0])+1):
    for b in range(len(stuff[1])+1):
        for c in range(len(stuff[2])+1):
            for d in range(len(stuff[3])+1):

                if w1*a + (w1+1)*b + (w1+2)*c + (w1+3)*d <= W:
                    ans = max(ans,sum(stuff[0][:a])+sum(stuff[1][:b])+sum(stuff[2][:c])+sum(stuff[3][:d]))
        

print(ans)

Submission status: Wrong Answer

Solution code:
n,w_sum=map(int,input().split())
from heapq import heappush,heappop
WV=[]
for i in range(n):
    w1,v1=map(int,input().split())
    WV.append((w1,v1))
dp={}
dp[0]=0
for w,v in WV:
    ndp=dp.copy()
    for i in ndp:
        if i+w>w_sum:
            continue 
        temp=dp[i]
        try:
            use=dp[i+w]
            dp[i+w]+=max(temp+v-use,0)
        except:
            dp[i+w]=temp+v 
    
ans=[]
for i in dp:
    heappush(ans,-dp[i])

print(-heappop(ans))

Submission status: Wrong Answer

Solution code:
n,w_sum=map(int,input().split())
from heapq import heappush,heappop
WV=[]
for i in range(n):
    w,v=map(int,input().split())
    WV.append((w,v))
dp={}
dp[0]=0
for w,v in WV:
    ndp=dp.copy()
    #print(dp)
    for i in ndp:
        if i+w>w_sum:
            continue 
        temp=dp[i]
        #print(temp)
        try:
            use=dp[i+w]
            #print(use)
            dp[i+w]+=max(temp+v-use,0)
        except:
            dp[i+w]=temp+v 
    
ans=[]

for i in dp:
    heappush(ans,-dp[i])
#print(ans)
print(-heappop(ans))

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
from heapq import heappush,heappop
WV=[]
for i in range(n):
    w,v=map(int,input().split())
    WV.append((w,v))
dp={}
dp[0]=0
for w,v in WV:
    ndp=dp.copy()
    for i in ndp:
        if i+w>w:
            continue 
        temp=dp[i]
        try:
            use=dp[i+w]
            dp[i+w]+=max(temp+v-use,0)
        except:
            dp[i+w]=temp+v 
    
ans=[]
for i in dp:
    heappush(ans,-dp[i])

print(-heappop(ans))

Submission status: Wrong Answer

Solution code:
n,weight = map(int, input().split())
wv=[list(map(int,input().split())) for i in range(n)]
w1=wv[0][0]

from collections import defaultdict
vals = defaultdict(list)
for tmp in wv:
    w,v=tmp
    vals[w-w1].append(v)

v1=sorted(vals[0])
v2=sorted(vals[1])
v3=sorted(vals[2])
v4=sorted(vals[3])

ans=-1
for num1 in range(len(v1)+1):
    for num2 in range(len(v2)+1):
        for num3 in range(len(v3)+1):
            for num4 in range(len(v4)+1):
                sumw = num1*w1 + num2*(w1+1) + num3*(w1+2) + num4*(w1+3)
                if sumw <=weight:
                    sm = sum(v1[:num1]) + sum(v2[:num2]) +  sum(v3[:num3]) +  sum(v4[:num4])
                    ans=max(ans,sm)
print(ans)

Submission status: Wrong Answer

Solution code:
# AtCoder Regular Contest 073
# D - Simple Knapsack
# https://atcoder.jp/contests/arc073/tasks/arc073_b
from itertools import combinations_with_replacement, accumulate
N, W, *A = map(int, open(0).read().split())
w0 = A[0]
T = [[] for _ in [0]*4]
M = [0]*4

for w, v in zip(*[iter(A)]*2):
    T[w-w0].append(v)
    M[w-w0] += 1
for t in T:
    t.sort()

acm = [tuple(accumulate(t)) for t in T]
C = []

def rec(w=0, k=0, c=()):
    if k == 4:
        C.append(c)
        return
    for i in range(M[k]+1):
        w1 = w + i*(w0+k)
        if w1 > W:
            break
        rec(w1, k+1, c+(i,))

rec()

ans = 0
for c in C:
    ans = max(ans, sum(acm[i][n-1] if n > 0 else 0 for i, n in enumerate(c)))

print(ans)

Submission status: Wrong Answer

Solution code:
# AtCoder Regular Contest 073
# D - Simple Knapsack
# https://atcoder.jp/contests/arc073/tasks/arc073_b
from itertools import combinations_with_replacement
N, W, *A = map(int, open(0).read().split())
w0 = A[0]
T = [[] for _ in [0]*4]
M = [0]*4

for w, v in zip(*[iter(A)]*2):
    T[w-w0].append(v)
    M[w-w0] += 1
for t in T:
    t.sort()

ans = 0
for n in range(N+1):
    for cmb in combinations_with_replacement(range(4), n):
        if sum(cmb)+n*w0 > W:
            continue

        cnt = [0]*4
        val = 0
        for w in cmb:
            if cnt[w] >= M[w]:
                break

            val += T[w][cnt[w]]
            cnt[w] += 1
        else:
            ans = max(ans, val)

print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
weight = []
value = []
wv = [[] for _ in range(4)]

for _ in range(N):
    w, v = map(int, input().split())
    if not weight:
        w_1 = w
    weight.append(w)
    value.append(v)
    wv[w - w_1].append(v)

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

ans = 0

# print(w_1, w_1 + 1, w_1 + 2, w_1 + 3)

# 重さの種類は 4 種類しかない
# 100 個のボールに3つスラッシュをいれる（100_C_3）
# ooo_f_ooo_s_ooo_t_ooo
for i in range(N + 1):
    for j in range(N + 1 - i):
        for k in range(N + 1 - i - j):
            for l in range(N + 1 - (i + j + k)):
                flg = 0
                # 個数用意できるか
                kosuu = [i, j, k, l]
                for m in range(4):
                    if len(wv[m]) < kosuu[m]: 
                        flg = 1
                        break
                if flg: continue
                
                # 重さの確認
                w_cur = 0
                for m in range(4):
                    w_cur += weight[m] * kosuu[m]
                if w_cur > W: continue
                
                # 価値の更新
                v_cur = 0
                for m in range(4):
                    v_cur += sum(wv[m][0 : kosuu[m]])
                ans = max(v_cur, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
weight = []
value = []
wv = [[] for _ in range(4)]

for _ in range(N):
    w, v = map(int, input().split())
    if not weight:
        w_1 = w
    weight.append(w)
    value.append(v)
    wv[w - w_1].append(v)

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

ans = 0

# print(w_1, w_1 + 1, w_1 + 2, w_1 + 3)

# 重さの種類は 4 種類しかない
# 100 個のボールに3つスラッシュをいれる（100_C_3）
# ooo_f_ooo_s_ooo_t_ooo
for i in range(N + 1):
    for j in range(N + 1 - i):
        for k in range(N + 1 - i - j):
            for l in range(N + 1 - (i + j + k)):
                # print(i, j, k, l)
                flg = 0
                # 個数用意できるか
                kosuu = [i, j, k, l]
                for m in range(4):
                    if len(wv[m]) < kosuu[m]: 
                        flg = 1
                        break
                if flg: break
                # print("s")
                # 重さの確認
                w_cur = 0
                for m in range(4):
                    w_cur += weight[m] * kosuu[m]
                if w_cur > W: continue
                # 価値の更新
                v_cur = 0
                for m in range(4):
                    v_cur += sum(wv[m][0 : kosuu[m]])
                ans = max(v_cur, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
lb = []
for i in range(N):
  lb.append(list(map(int,input().split())))
 
lw = [0]
wo = lb[0][0]
for i in range(1,N+1):
  lw.append(wo*i)
  lw.append(wo*i+1)
  lw.append(wo*i+2)
  lw.append(wo*i+3)  
 
dp = [[0 for i in range(wo*N+3+1)] for j in range(N+1)]
 
for i in range(N):
  for k in range(len(lw)):
    w = lw[k]
    if w > W:
      dp[i][w] = dp[i][lw[k-1]]
      continue
    elif w-lb[i][0] >= 0:
      dp[i+1][w] = max(dp[i][w],dp[i][w-lb[i][0]]+lb[i][1]) 
    else:
      dp[i+1][w] = dp[i][w]
 
for k in range(len(lw)):
  w = lw[k]
  if w > W:
    dp[N][w] = dp[N][lw[k-1]]
    continue
    
 
print(dp[N][wo*N+3])

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
lb = []
for i in range(N):
  lb.append(list(map(int,input().split())))

lw = [0]
wo = lb[0][0]
for i in range(1,N+1):
  lw.append(wo*i)
  lw.append(wo*i+1)
  lw.append(wo*i+2)
  lw.append(wo*i+3)  

dp = [[0 for i in range(wo*N+3+1)] for j in range(N+1)]

for i in range(N):
  for k in range(len(lw)):
    w = lw[k]
    if w > W:
      dp[i][w] = dp[i][lw[k-1]]
      continue
    elif w-lb[i][0] >= 0:
      dp[i+1][w] = max(dp[i][w],dp[i][w-lb[i][0]]+lb[i][1]) 
    else:
      dp[i+1][w] = dp[i][w]

for k in range(len(lw)):
  w = lw[k]
  if w > W:
    dp[N][w] = dp[N][lw[k-1]]
    continue
    

print(dp[N][wo*N+3])

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,W = inpl() 
a = [inpl() for _ in range(n)]
a.sort(key = lambda x:x[1], reverse = True)
a.sort()
b = []
now = a[0][0]
li = []
for i in range(n):
    w,v = a[i]
    if now == w:
        li.append(v)
    else:
        now = w
        b.append(li)
        li = []
        li.append(v)
if li != []: b.append(li)
kind = now - a[0][0] + 1
f = a[0][0]
for i in range(len(b)):
    b[i] = b[i][::-1]

c = [[0] for _ in range(4)]
for i,l in enumerate(b):
    for x in l:
        c[i].append(c[i][-1] + x)
    c[i] = c[i]
print(c)
ln = [len(x) for x in c]
res = 0
def chk(w,v):
    global res
    if w <= W:
        res = max(res, v)
x,y,z,w = ln
print(ln)
for i in range(x):
    for j in range(y):
        for k in range(z):
            for l in range(w):
                ww = i*f+j*(f+1)+k*(f+2)+l*(f+3)
                v = c[0][i] + c[1][j] + c[2][k] + c[3][l]
                if ww <= W: res = max(res, v)
                # print(ww,v)
print(res)

Submission status: Wrong Answer

Solution code:
def main():
    n, w_lim = map(int, input().split())
    group = {}
    min_w = 0
    for i in range(n):
        w, v = map(int, input().split())
        if i == 0:
            group = {x: [0] for x in range(w, w + 4)}
            min_w = w
        group[w].append(v)
    length = [len(group[i]) for i in range(min_w, min_w + 4)]
    for i in range(min_w, min_w + 4):
        group[i].sort()
        for j in range(1, length[i - min_w]):
            group[i][j] += group[i][j - 1]
    answer = 0
    for i in range(length[0]):
        for j in range(length[1]):
            for k in range(length[2]):
                for l in range(length[3]):
                    if w_lim < min_w * i + (min_w + 1) * j + (min_w + 2) * k + (min_w + 3) * l:
                        continue
                    answer = max(answer, group[min_w][i] + group[min_w + 1][j] + group[min_w + 2][k] + group[min_w + 3][l])
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
WV = [[int(i) for i in input().split()] for _ in range(N)]

MINW = WV[0][0]

W0,W1,W2,W3 = [],[],[],[]
for w,v in WV:
    if w == MINW: W0.append(v)
    elif w == MINW + 1: W1.append(v)
    elif w == MINW + 2: W2.append(v)
    elif w == MINW + 3: W3.append(v)

W0.sort(reverse=True)
W1.sort(reverse=True)
W2.sort(reverse=True)
W3.sort(reverse=True)

W0 = [0] + W0
W0 = [0] + W1
W0 = [0] + W2
W0 = [0] + W3

from itertools import accumulate

W0 = list(accumulate(W0))
W1 = list(accumulate(W1))
W2 = list(accumulate(W2))
W3 = list(accumulate(W3))

ans = 0
for cnt0 in range(len(W0)):
    for cnt1 in range(len(W1)):
        for cnt2 in range(len(W2)):
            for cnt3 in range(len(W3)):
                SUMW = cnt0 * MINW
                SUMW += cnt1 * (MINW + 1)
                SUMW += cnt2 * (MINW + 2)
                SUMW += cnt3 * (MINW + 3)

                if SUMW <= W:
                    SUMV = W0[cnt0]
                    SUMV += W1[cnt1]
                    SUMV += W2[cnt2]
                    SUMV += W3[cnt3]
                    ans = max(ans, SUMV)

print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
WV = [[int(i) for i in input().split()] for _ in range(N)]

MINW = WV[0][0]

W0,W1,W2,W3 = [0],[0],[0],[0]
for w,v in WV:
    if w == MINW: W0.append(v)
    elif w == MINW + 1: W1.append(v)
    elif w == MINW + 2: W2.append(v)
    elif w == MINW + 3: W3.append(v)

W0.sort(); W1.sort(); W2.sort(); W3.sort()

from itertools import accumulate

W0 = list(accumulate(W0))
W1 = list(accumulate(W1))
W2 = list(accumulate(W2))
W3 = list(accumulate(W3))

ans = 0
for cnt0 in range(len(W0)):
    for cnt1 in range(len(W1)):
        for cnt2 in range(len(W2)):
            for cnt3 in range(len(W3)):
                SUMW = cnt0 * MINW
                SUMW += cnt1 * (MINW + 1)
                SUMW += cnt2 * (MINW + 2)
                SUMW += cnt3 * (MINW + 3)

                if SUMW <= W:
                    SUMV = W0[cnt0]
                    SUMV += W1[cnt1]
                    SUMV += W2[cnt2]
                    SUMV += W3[cnt3]
                    ans = max(ans, SUMV)

print(ans)

Submission status: Wrong Answer

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

N, W = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(N)]
w1 = wv[0][0]
dp = [[0] * 301 for _ in range(N+1)]
for w, v in wv:
    w -= w1
    for i in range(1, N+1)[::-1]:
        for j in range(w, 301):
            dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v)
ans = 0
for i in range(N+1):
    w = W - w1*i
    if 0 <= w <= 300:
        ans = max(ans, dp[i][W-w1*i])
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+10) 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):
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
            if dp[i][n][j] == -1: continue
            if j + n*ws[0] + w <= W:
                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 = min(W - i*ws[0], sum(ws_m))
    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+10) 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):
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
            if dp[i][n][j] == -1: continue
            if j + n*ws[0] + w <= W:
                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 = [[[0]*(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):
            # もらうDP
            # j-wなら、新しくwをナップサックに入れて価値が増えるか見る
            if j-w >= 0:
                dp[i+1][n+1][j] = max(dp[i][n+1][j], dp[i][n][j-w]+v)
            # 追加できない場合は以前の情報を更新
            else:
                dp[i+1][n+1][j] = dp[i][n+1][j]
            # 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)
        # print(dp[i+1][n])
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,-1,-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][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)