Problem:


Score : 400 points

Problem Statement

You have N items and a bag of strength W.
The i-th item has a weight of w_i and a value of v_i.

You will select some of the items and put them in the bag.
Here, the total weight of the selected items needs to be at most W.

Your objective is to maximize the total value of the selected items.

Constraints

1 ≤ N ≤ 100

1 ≤ W ≤ 10^9

1 ≤ w_i ≤ 10^9

For each i = 2,3,...,N, w_1 ≤ w_i ≤ w_1 + 3.

1 ≤ v_i ≤ 10^7

W, each w_i and v_i are integers.

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible total value of the selected items.

Sample Input 1

4 6
2 1
3 4
4 10
3 4

Sample Output 1

11

The first and third items should be selected.

Sample Input 2

4 6
2 1
3 7
4 10
3 6

Sample Output 2

13

The second and fourth items should be selected.

Sample Input 3

4 10
1 100
1 100
1 100
1 100

Sample Output 3

400

You can take everything.

Sample Input 4

4 1
10 100
10 100
10 100
10 100

Sample Output 4

0

You can take nothing.



Sample input:
4 6
2 1
3 4
4 10
3 4


Sample output:
11

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w_list = []
v_list = []
for i in range(N):
    w, v = map(int, input().split())
    w_list += [w]
    v_list += [v]
w0 = w_list[0] - 1
ans = 0
for c in range(N+1):
    wc = W - c * w0
    if wc <= 0:
        break
    wc = min(wc, 4*c)
    dp = [[0 for j in range(wc+1)] for i in range(N+1)]
    ct = [[0 for j in range(wc+1)] for i in range(N+1)]
    for i in range(N):
        wi = w_list[i] - w0
        vi = v_list[i]
        for j in range(wc+1):
            if j - wi >= 0 and ct[i][j-wi] < c and dp[i][j] < dp[i][j-wi]+vi:
                dp[i+1][j] = dp[i][j-wi]+vi
                ct[i+1][j] = ct[i][j-wi]+1
            elif j > 0 and dp[i][j] < dp[i+1][j-1]:
                dp[i+1][j] = dp[i+1][j-1]
                ct[i+1][j] = ct[i+1][j-1]
            else:
                dp[i+1][j] = dp[i][j]
                ct[i+1][j] = ct[i][j]
    
    # ans = max(ans, max([x for row in dp for x in row]))
    ans = max(ans, dp[-1][-1])
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w_list = []
v_list = []
for i in range(N):
    w, v = map(int, input().split())
    w_list += [w]
    v_list += [v]
w0 = w_list[0] - 1
ans = 0
for c in range(N+1):
    wc = W - c * w0
    if wc <= 0:
        break
    wc = min(wc, 4*c)
    dp = [[0 for j in range(wc+1)] for i in range(N+1)]
    ct = [[0 for j in range(wc+1)] for i in range(N+1)]
    for i in range(N):
        wi = w_list[i] - w0
        vi = v_list[i]
        for j in range(wc+1):
            if j - wi >= 0 and ct[i][j-wi] < c and dp[i][j] < dp[i][j-wi]+vi:
                dp[i+1][j] = dp[i][j-wi]+vi
                ct[i+1][j] = ct[i][j-wi]+1
            else:
                dp[i+1][j] = dp[i][j]
                ct[i+1][j] = ct[i][j]
    
    ans = max(ans, max([x for row in dp for x in row]))
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w_list = []
v_list = []
for i in range(N):
    w, v = map(int, input().split())
    w_list += [w]
    v_list += [v]
w0 = w_list[0] - 1
ans = 0
for c in range(N+1):
    wc = W - c * w0
    if wc < 0:
        break
    wc = min(wc, 4*c)
    dp = [[0 for j in range(wc+1)] for i in range(N+1)]
    ct = [[0 for j in range(wc+1)] for i in range(N+1)]
    for i in range(N):
        wi = w_list[i] - w0
        vi = v_list[i]
        for j in range(wc+1):
            if j - wi >= 0 and ct[i][j-wi] < c and dp[i][j] < dp[i][j-wi]+vi:
                dp[i+1][j] = dp[i][j-wi]+vi
                ct[i+1][j] = ct[i][j-wi]+1
            else:
                dp[i+1][j] = dp[i][j]
                ct[i+1][j] = ct[i][j]
    
    ans = max(ans, max([x for row in dp for x in row]))
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w_list = []
v_list = []
for i in range(N):
    w, v = map(int, input().split())
    w_list += [w]
    v_list += [v]
w0 = w_list[0] - 1
ans = 0
for c in range(N+1):
    wc = W - c * w0
    if wc < 0:
        break
    wc = min(wc, 4*c)
    dp = [[0 for j in range(wc+1)] for i in range(N+1)]
    ct = [[0 for j in range(wc+1)] for i in range(N+1)]
    for i in range(N):
        wi = w_list[i] - w0
        vi = v_list[i]
        for j in range(wc+1):
            if j - wi >= 0 and ct[i][j-wi] < c and dp[i][j] < dp[i][j-wi]+vi:
                dp[i+1][j] = dp[i][j-wi]+vi
                ct[i+1][j] = ct[i][j-wi]+1
            else:
                dp[i+1][j] = dp[i][j]
                ct[i+1][j] = ct[i][j]
    ans = max(ans, max(dp[-1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w_list = []
v_list = []
for i in range(N):
    w, v = map(int, input().split())
    w_list += [w]
    v_list += [v]
w0 = w_list[0] - 1
ans = 0
for c in range(N+1):
    wc = W - c * w0
    if wc < 0:
        break
    wc = min(wc, 4*c)
    dp = [[0 for j in range(wc+1)] for i in range(N+1)]
    ct = [[0 for j in range(wc+1)] for i in range(N+1)]
    for i in range(N):
        wi = w_list[i] - w0
        vi = v_list[i]
        for j in range(wc+1):
            if j - wi >= 0 and ct[i][j-wi] < c and dp[i][j] < dp[i][j-wi]+vi:
                dp[i+1][j] = dp[i][j-wi]+vi
                ct[i+1][j] = ct[i][j-wi]+1
            else:
                dp[i+1][j] = dp[i][j]
                ct[i+1][j] = ct[i][j]

    ans = max(ans, dp[-1][-1])
print(ans)

Submission status: Wrong Answer

Solution code:
#DP[i][j][k] = (i番目まで、j個選ぶ、有効重さの和kのときの最大得点)

N, W = map(int, input().split())
INF = 10**13
DP = [[[-INF for _ in range(3*N+1)] for _ in range(N+1)] for _ in range(N+1)]
w0, v = map(int, input().split())
DP[1][0][0] = 0
DP[1][1][0] = v

for i in range(2,N+1):
  w, v = map(int, input().split())
  w -= w0
  for j in range(1,N+1):
    for k in range(3*N+1):
      if k-w >= 0:
        DP[i][j][k] = max(DP[i-1][j-1][k-w] + v, DP[i-1][j][k])
      else:
        DP[i][j][k] = DP[i-1][j][k]

#print(w0)
#print(DP)
#print([max(DP[N][j]) + w0*j for j in range(N+1)])
#print(max([max(DP[N][j]) + w0*j for j in range(N+1)]))
print(max([max([DP[N][j][k] for k in range(min(3*N,W-w0*j)+1)]) if W-w0*j >= 0 else -INF for j in range(N+1)]))

Submission status: Wrong Answer

Solution code:
n,w=map(int, input().split())

weight=[]
value=[]
for _ in range(n):
    _w,_v=map(int, input().split())
    weight.append(_w)
    value.append(_v)


def knapsack(n, w, weight, value):
    # 初期化
    _dp = [[-float("inf") for _ in range(w+1)] for _ in range(n+1)]
    for _i in range(w+1):
        _dp[0][_i] = 0

    # DP
    for _i in range(n):
        for _j in range(w+1):
            # dp[i][w-weight[i]] の状態にi番目の荷物が入る可能性がある
            if weight[_i] <= _j:
                _dp[_i+1][_j] = max(_dp[_i][w-weight[_i]]+value[_i], _dp[_i][_j])
            else:  # 入る可能性はない
                _dp[_i+1][_j] = _dp[_i][_j]
    # print(_dp)
    return _dp[n][w]


print(knapsack(n,w,weight,value))

Submission status: Wrong Answer

Solution code:
# 普通のナップサックは O(荷物の数、ナップサックに入る重量の上限)で計算できる。
# 今回はこれだと O(100 * 10**9) なので無理。
# 明らかに条件で重要なのは「すべてのi=2,3,...,Nについて、w_1<=w_i<=w_1+3」

# w_1が1000とする
# W = 4500→4つが必ず入り、5つは必ず入らない。価値の高いものから4つ。
# W = 4005→3つが必ず入る。4つが入るかどうかは場合による。
# max(3つの場合, 4つの場合)。3つは価値の高いものから3つ。4つは?
# 4つ選ぶ、4005以下、価値最大化
# dp[i][k][l]

# w_1〜w_iの中からk個選んで、重量をちょうどlにしたときの、最大価値
# dp[i][k][l] := max(dp[i-1][k][l], dp[i-1][k-1][l - w_i] + v_i)

# w_1〜w_iの中からk個選んで、重量をl以下にしたときの、最大価値
# dp[i][k][l] := max(dp[i-1][k][l], dp[i-1][k-1][l - w_i] + v_i)

# 後者を使うべき。更新式は同じで最後に重量に関してmaxを取る手間が無いので。
# i <= N, k <= N, l <= 3*N

n, w_limit = list(map(int, input().split()))

baggage = [list(map(int, input().split())) for _ in range(n)]

weight_base = baggage[0][0]

# i添字は0〜n-1 問題文から1引いて0-indexにする
# k添字は0〜n 
# l添字は0〜3n

for i in range(n):
    baggage[i][0] -= weight_base

dp = [[[0 for _ in range(3*n+1)] for _ in range(n+1)] for _ in range(n)]

for l in range(baggage[0][0], 3*n):
    dp[0][1][l] = baggage[0][1]

for i in range(1, n):
    for k in range(1, n+1):
        for l in range(3*n+1):
            if l - baggage[i][0] >= 0:
                dp[i][k][l] = max(dp[i-1][k][l], dp[i-1][k-1][l - baggage[i][0]] + baggage[i][1])
            else:
                dp[i][k][l] = dp[i-1][k][l]

valid_min_num = w_limit // (weight_base+3)
valid_max_num = w_limit // weight_base

ans = 0
for num in range(valid_min_num, min(valid_max_num, n) + 1):
    weight_rest = w_limit - weight_base * num
    if not 0 <= weight_rest <= 3*n:
        continue
    # print(n-1, num, weight_rest)
    ans = max(ans, dp[n-1][num][weight_rest])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()
offset = 10**10

def main():
    """
    ナップサックで重さを飛び飛びにしてdpを軽くしなくても、
    そもそも重さが４パターンだから全探索で解けたのか。。。。。。
    """
    N, W = map(int, input().split())
    item = [[] for _ in range(4)]
    length = [1, 0, 0, 0]
    w0, v0 = map(int, input().split())
    item[0].append(v0)
    for _ in range(N - 1):
        w, v = map(int, input().split())
        item[w - w0].append(v)
        length[w - w0] += 1
    for i in range(4): item[i].sort(reverse=True)

    # 重さの累積和
    S = []
    for i in range(4):
        S.append([0] + list(accumulate(item[i])))
    print(item)
    print(S)

    ans = 0
    for a in range(length[0] + 1):
        for b in range(length[1] + 1):
            for c in range(length[2] + 1):
                for d in range(length[3] + 1):
                    weight = a * w0 + b * (w0 + 1) + c * (w0 + 2) + d * (w0 + 3)
                    if weight > W: continue
                    ans = max(ans, S[0][a] + S[1][b] + S[2][c] + S[3][d])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,W = MI()
w1,v = MI()
v0,v1,v2 = [v],[],[]  # 重さが w1,w1+1,w1+2 である荷物の価値
for i in range(N-1):
    w,v = MI()
    if w == w1:
        v0.append(v)
    elif w == w1+1:
        v1.append(v)
    else:
        v2.append(v)

v0.sort(reverse=True)
v1.sort(reverse=True)
v2.sort(reverse=True)
N0,N1,N2 = len(v0),len(v1),len(v2)

from itertools import accumulate
v0_accumulate = [0] + list(accumulate(v0))
v1_accumulate = [0] + list(accumulate(v1))
v2_accumulate = [0] + list(accumulate(v2))

ans = 0
for i in range(N0+1):  # 重さが w1 である荷物を i 個選ぶ
    for j in range(N1+1):  # 重さが w1+1 である荷物を j 個選ぶ
        for k in range(N2+1):  # 重さが w1+2 である荷物を k 個選ぶ
            if w1*i + (w1+1)*j + (w1+2)*k <= W:
                ans = max(ans,v0_accumulate[i]+v1_accumulate[j]+v2_accumulate[k])
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np

def main():
    def itrsum(arr):
        n=len(arr)
        tri=np.array([[i>=j for i in range(n)] for j in range(n+1)])
        return np.dot(tri,arr).astype('int64')
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    # arr=[sorted([x for x in t if x[0]==w1+i],reverse=True,key=lambda e:e[1]) for i in range(4)]
    arr=[[x for x in t if x[0]==w1+i] for i in range(4)]
    arr=[l for l in arr]
    lenarr=list(map(len,arr))
    arr0=[itrsum(np.array([x[0] for x in l],dtype='int64')) for l in arr]
    arr1=[itrsum(np.array([x[1] for x in l],dtype='int64')) for l in arr]
    # arr=[x.sort(reverse=True,key=lambda e:e[1]) for x in arr]
    arr=np.array(arr)
    arrw=0
    arrv=0
    for i in range(4):
        arrw=np.ravel(arr0[i].reshape(lenarr[i]+1,1)+np.array([arrw]))
        arrv=np.ravel(arr1[i].reshape(lenarr[i]+1,1)+np.array([arrv]))
    #print(arr0)
    #print(arr1)
    #print('\n')
    #print(arrw)
    #print(arrv)
    #print(arrv[arrw<=w])
    ansarr=arrv[arrw<=w]
    print(np.max(ansarr))
    # wts=list(map(lambda l:l[0]-w1-1, t))
    # val=list(map(lambda l:l[1], t))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    wts=list(map(lambda l:l[0]-w1+1, t))
    val=list(map(lambda l:l[1], t))
    m=4*n+1
    dp=[[[0,0] for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if i>0:
                if j>=wts[i] and dp[i-1][j][0]<dp[i-1][j-wts[i]][0]+val[i] and dp[i-1][j-wts[i]][1]+wts[i]+w1-1<=w:
                    dp[i][j][0]=dp[i-1][j-wts[i]][0]+val[i]
                    dp[i][j][1]=dp[i-1][j-wts[i]][1]+wts[i]+w1-1
                else:
                    dp[i][j]=dp[i-1][j]
            else:
                if w1<=w and j>0:
                    dp[0][j][0]=val[0]
                    dp[0][j][1]=w1
        # print(dp[i][:])
    print(max([dp[n-1][j][0] for j in range(m)]))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    wts=list(map(lambda l:l[0]-w1+1, t))
    val=list(map(lambda l:l[1], t))
    m=3*n+1
    dp=[[[0,0] for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if i>0:
                if j>=wts[i] and dp[i-1][j][0]<dp[i-1][j-wts[i]][0]+val[i] and dp[i-1][j-wts[i]][1]+wts[i]+w1-1<=w:
                    dp[i][j][0]=dp[i-1][j-wts[i]][0]+val[i]
                    dp[i][j][1]=dp[i-1][j-wts[i]][1]+wts[i]+w1-1
                else:
                    dp[i][j]=dp[i-1][j]
            else:
                if w1<=w and j>0:
                    dp[0][j][0]=val[0]
                    dp[0][j][1]=w1
        # print(dp[i][:])
    print(max([dp[n-1][j][0] for j in range(m)]))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    wts=list(map(lambda l:l[0]-w1, t))
    val=list(map(lambda l:l[1], t))
    m=3*n+1
    dp=[[[0,0] for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if i>0:
                if j>=wts[i] and dp[i-1][j][0]<dp[i-1][j-wts[i]][0]+val[i] and dp[i-1][j-wts[i]][1]+wts[i]+w1<=w:
                    dp[i][j][0]=dp[i-1][j-wts[i]][0]+val[i]
                    dp[i][j][1]=dp[i-1][j-wts[i]][1]+wts[i]+w1
                else:
                    dp[i][j]=dp[i-1][j]
            else:
                if w1<=w:
                    dp[0][j][0]=val[0]
                    dp[0][j][1]=w1
        # print(dp[i][:])
    print(max([dp[n-1][j][0] for j in range(m)]))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    wts=list(map(lambda l:l[0]-w1, t))
    val=list(map(lambda l:l[1], t))
    m=3*n+1
    dp=[[[0,0] for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if i>0:
                if j>=wts[i] and dp[i-1][j][0]<dp[i-1][j-wts[i]][0]+val[i] and dp[i-1][j-wts[i]][1]+wts[i]+w1<=w:
                    dp[i][j][0]=dp[i-1][j-wts[i]][0]+val[i]
                    dp[i][j][1]=dp[i-1][j-wts[i]][1]+wts[i]+w1
                else:
                    dp[i][j]=dp[i-1][j]
            else:
                if w1<=w:
                    dp[0][0][0]=val[0]
                    dp[0][0][1]=w1
        # print(dp[i][:])
    print(max([dp[n-1][j][0] for j in range(m)]))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    wts=list(map(lambda l:l[0]-w1, t))
    val=list(map(lambda l:l[1], t))
    m=3*n+1
    dp=[[[0,0] for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if i>0:
                if j>=wts[i] and dp[i-1][j][0]<dp[i-1][j-wts[i]][0]+val[i] and dp[i-1][j-wts[i]][1]+wts[i]+w1<=w:
                    dp[i][j][0]=dp[i-1][j-wts[i]][0]+val[i]
                    dp[i][j][1]=dp[i-1][j-wts[i]][1]+wts[i]+w1
                else:
                    dp[i][j]=dp[i-1][j]
            else:
                if w1<=w:
                    dp[0][0][0]=val[0]
                    dp[0][0][1]=w1
        # print(dp[i][:])
    print(dp[n-1][m-1][0])

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    wts=list(map(lambda l:l[0]-w1+1, t))
    val=list(map(lambda l:l[1], t))
    m=4*n+1
    dp=[[[0,0] for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if i>0 and j>=wts[i] and dp[i-1][j-wts[i]][1]>0:
                if dp[i-1][j][0]<dp[i-1][j-wts[i]][0]+val[i] and dp[i-1][j-wts[i]][1]+wts[i]+w1-1<=w:
                    dp[i][j][0]=dp[i-1][j-wts[i]][0]+val[i]
                    dp[i][j][1]=dp[i-1][j-wts[i]][1]+wts[i]+w1-1
                else:
                    dp[i][j]=dp[i-1][j]
            elif i>0:
                dp[i][j]=dp[i-1][j]
            elif i==0 and j==1 and w1<=w:
                dp[0][1][0]=val[0]
                dp[0][1][1]=w1
        # print(dp[i][:])
    print(max([dp[n-1][j][0] for j in range(m)]))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    wts=list(map(lambda l:l[0]-w1, t))
    val=list(map(lambda l:l[1], t))
    minf=-10**12
    m=3*n+1
    dp=[[[0,0]]*m for _ in range(n)]
    if w1<=w:
        dp[0][0]=[val[0],w1]
    # print(dp[0][:])
    for i in range(1,n):
        for j in range(m):
            if j>=wts[i] and dp[i-1][j-wts[i]][0]>=0:
                if dp[i-1][j][0]<dp[i-1][j-wts[i]][0]+val[i] and dp[i-1][j-wts[i]][1]+wts[i]+w1<=w:
                    dp[i][j]=[dp[i-1][j-wts[i]][0]+val[i],dp[i-1][j-wts[i]][1]+wts[i]+w1]
                else:
                    dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=dp[i-1][j]
        # print(dp[i][:])
    print(max([dp[i][j][0] for i in range(n) for j in range(m) if dp[i][j][1]<=w]))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    wts=list(map(lambda l:l[0]-w1, t))
    val=list(map(lambda l:l[1], t))
    minf=-10**12
    m=3*n+1
    dp=[[[-1,-1]]*m for _ in range(n)]
    if w1<=w:
        dp[0][0]=[val[0],w1]
    # print(dp[0][:])
    for i in range(1,n):
        for j in range(m):
            if j>=wts[i] and dp[i-1][j-wts[i]][0]>=0:
                if dp[i-1][j][0]<dp[i-1][j-wts[i]][0]+val[i] and dp[i-1][j-wts[i]][1]+wts[i]+w1<=w:
                    dp[i][j]=[dp[i-1][j-wts[i]][0]+val[i],dp[i-1][j-wts[i]][1]+wts[i]+w1]
                else:
                    dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=dp[i-1][j]
        # print(dp[i][:])
    print(max([dp[i][j][0] for i in range(n) for j in range(m) if dp[i][j][1]<=w]))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    wts=list(map(lambda l:l[0]-w1, t))
    val=list(map(lambda l:l[1], t))
    minf=-10**12
    m=3*n+1
    dp=[[[minf,0]]*m for _ in range(n)]
    if w1<=w:
        dp[0][0]=[val[0],w1]
    # print(dp[0][:])
    for i in range(1,n):
        for j in range(m):
            if j>=wts[i]:
                if dp[i-1][j][0]<dp[i-1][j-wts[i]][0]+val[i] and dp[i-1][j-wts[i]][1]+wts[i]+w1<=w:
                    dp[i][j]=[dp[i-1][j-wts[i]][0]+val[i],dp[i-1][j-wts[i]][1]+wts[i]+w1]
                else:
                    dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=dp[i-1][j]
            if dp[i][j][0]<0:
                dp[i][j][0]=minf
        #print(dp[i][:])
    print(max([dp[n-1][j][0] for j in range(m)]))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    wts=list(map(lambda l:l[0]-w1, t))
    val=list(map(lambda l:l[1], t))
    minf=-10**10
    m=3*n+1
    dp=[[[minf,0]]*m for _ in range(n)]
    if w1<=w:
        dp[0][0]=[val[0],w1]
    # print(dp[0][:])
    for i in range(1,n):
        for j in range(m):
            if j>=wts[i]:
                if dp[i-1][j][0]<dp[i-1][j-wts[i]][0]+val[i] and dp[i-1][j-wts[i]][1]+wts[i]+w1<=w:
                    dp[i][j]=[dp[i-1][j-wts[i]][0]+val[i],dp[i-1][j-wts[i]][1]+wts[i]+w1]
                else:
                    dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=dp[i-1][j]
            if dp[i][j][0]<0:
                dp[i][j][0]=minf
        #print(dp[i][:])
    print(max([dp[n-1][j][0] for j in range(m)]))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    wts=list(map(lambda l:l[0]-w1, t))
    val=list(map(lambda l:l[1], t))
    minf=-10**9
    m=3*n+1
    dp=[[[minf,0]]*m for _ in range(n)]
    if w1<=w:
        dp[0][0]=[val[0],w1]
    # print(dp[0][:])
    for i in range(1,n):
        for j in range(m):
            if j>=wts[i]:
                if dp[i-1][j][0]<dp[i-1][j-wts[i]][0]+val[i] and dp[i-1][j-wts[i]][1]+wts[i]+w1<=w:
                    dp[i][j]=[dp[i-1][j-wts[i]][0]+val[i],dp[i-1][j-wts[i]][1]+wts[i]+w1]
                else:
                    dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=dp[i-1][j]
            if dp[i][j][0]<0:
                dp[i][j][0]=minf
        #print(dp[i][:])
    print(max([dp[n-1][j][0] for j in range(m)]))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    wts=list(map(lambda l:l[0]-w1, t))
    val=list(map(lambda l:l[1], t))
    minf=-10**9
    m=3*n+1
    dp=[[[minf,0]]*m for _ in range(n)]
    if w1<=w:
        dp[0][0]=[val[0],w1]
    print(dp[0][:])
    for i in range(1,n):
        for j in range(m):
            if j>=wts[i]:
                if dp[i-1][j][0]<dp[i-1][j-wts[i]][0]+val[i] and dp[i-1][j-wts[i]][1]+wts[i]+w1<=w:
                    dp[i][j]=[dp[i-1][j-wts[i]][0]+val[i],dp[i-1][j-wts[i]][1]+wts[i]+w1]
                else:
                    dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=dp[i-1][j]
            if dp[i][j][0]<0:
                dp[i][j][0]=minf
        #print(dp[i][:])
    print(max([dp[n-1][j][0] for j in range(m)]))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    wts=list(map(lambda l:l[0]-w1, t))
    val=list(map(lambda l:l[1], t))
    m=3*n+1
    dp=[[[0,0]]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if i==0 and j==0 and w1<=w:
                dp[i][j]=[val[i],w1]
            elif i>0 and j>=wts[i]:
                if dp[i-1][j][0]<dp[i-1][j-wts[i]][0]+val[i] and dp[i-1][j-wts[i]][1]+wts[i]+w1<=w:
                    dp[i][j]=[dp[i-1][j-wts[i]][0]+val[i],dp[i-1][j-wts[i]][1]+wts[i]+w1]
                else:
                    dp[i][j]=dp[i-1][j]
            elif i>0:
                dp[i][j]=dp[i-1][j]
        # print(dp[i][:])
    print(max([dp[n-1][j][0] for j in range(m)]))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    wts=list(map(lambda l:l[0]-w1, t))
    val=list(map(lambda l:l[1], t))
    m=3*n+1
    dp=[[[0,0]]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if i==0 and j==0 and w1<=w:
                dp[i][j]=[val[i],w1]
            elif i>0 and j>=wts[i]:
                if dp[i-1][j][0]<=dp[i-1][j-wts[i]][0]+val[i] and dp[i-1][j-wts[i]][1]+wts[i]+w1<=w:
                    dp[i][j]=[dp[i-1][j-wts[i]][0]+val[i],dp[i-1][j-wts[i]][1]+wts[i]+w1]
                else:
                    dp[i][j]=dp[i-1][j]
            elif i>0:
                dp[i][j]=dp[i-1][j]
        # print(dp[i][:])
    print(max([dp[n-1][j][0] for j in range(m)]))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().rstrip().split(" "))
DP = [[-1 for _ in range(301)] for _ in range(N+1)]
DP[0][0] = 0
ans = 0
for i in range(N):
    w,v = map(int,input().rstrip().split(" "))
    if i == 0: w1 = w
    for i2 in range(i+1):
        for i3 in range(301):
            if DP[i2][i3] != -1:
                DP[i2 + 1][i3 + (w - w1)] = max(DP[i2 + 1][i3 + (w - w1)],DP[i2][i3]+v)
                if i2 * w1 + i3 + w <= W:
                    ans = max(DP[i2 + 1][i3 + (w - w1)],ans)
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())

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

print(dp[N][min(W,10000)])

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

dp = [[0] * 10010 for _ in range(N+1)]
minw = min(w)
for i in range(N):
    w[i] -= minw
    w[i] += 1
for i in range(N):
    for j in range(10000):
        dp[i+1][j] = dp[i][j]
        if j-w[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]]+v[i])
    
print(dp[N][min(max(0, W-minw),10000)])

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
w0 = wv[0][0]
wv.sort()
w1, w2, w3, w4 = [], [], [], []
for w, v in wv:
    if w == w0:
        w1.append(v)
    elif w == w0 + 1:
        w2.append(v)
    elif w == w0 + 2:
        w3.append(v)
    else:
        w4.append(v)
Sw1, Sw2, Sw3, Sw4 = [0], [0], [0], [0]
S = 0
for v in w1:
    S += v
    Sw1.append(S)
S = 0
for v in w2:
    S += v
    Sw2.append(S)
S = 0
for v in w3:
    S += v
    Sw3.append(S)
S = 0
for v in w4:
    S += v
    Sw4.append(S)
l1, l2, l3, l4 = len(w1), len(w2), len(w3), len(w4)
V = 0
v = 0
for i in range(l1 + 1):
    if w0 * i > W:
        break
    for j in range(l2 + 1):
        if w0 * i + (w0 + 1) * j > W:
            break
        for k in range(l3 + 1):
            if w0 * i + (w0 + 1) * j + (w0 + 2) * k > W:
                break
            for l in range(l4 + 1):
                if w0 * i + (w0 + 1) * j + (w0 + 2) * k + (w0 + 3) * l > W:
                    break
                v = Sw1[i] + Sw2[j] + Sw3[k] + Sw4[l]
                V = max(V, v)
print(V)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N,W = map(int,readline().split())
goods = [tuple(map(int,readline().split())) for i in range(N)]

from collections import defaultdict

d = defaultdict(int)
d[0] = 0

for (w,v) in goods:
    dnew = defaultdict(int)
    for key,value in d.items():
        dnew[key] = value
    for key,value in d.items():
        dnew[key+w] = max(dnew[key+w],dnew[key]+v)
    d = dnew
ans = 0
for k,v in d.items():
    if k <= W:
        ans = max(ans,v)
print(ans)

Submission status: Wrong Answer

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

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

M = 0
for i in range(4 * N):
    if i + w1 <= W:
        M = max(M, dp[-1][i])
print(M)

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
w=[0 for i in range(n)]
v=[[] for i in range(4)]
dp=[[0] for i in range(4)]
for i in range(n):
  w[i],vi=map(int,input().split())
  v[w[i]-w[0]].append(vi)
for i in range(4):
  v[i].sort(reverse=True)
  for j in v[i]:
    dp[i].append(dp[i][-1]+j)

def dfs(i,cost):
  if i==4:
    return 0
  if cost>W:
    return -10**10
  else:
    val=0
    for j in range(len(dp[i])):
      val=max(val,dp[i][j]+dfs(i+1,cost+j*(w[0]+i)))
    return val
print(dfs(0,0))

Submission status: Wrong Answer

Solution code:
n,w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [[] for _ in range(4)]
for i,j in a:
    b[i-a[0][0]].append(j)
for i in range(4):
    b[i].sort()
    b[i].reverse()
for i in range(4):
    for j in range(1,len(b[i])):
        b[i][j] += b[i][j-1]
    b[i].reverse()
    b[i].append(0)
    b[i].reverse()
ans = 0
for i in range(len(b[0])):
    for j in range(len(b[1])):
        for k in range(len(b[2])):
            for l in range(len(b[3])):
                if a[0][0]*i+(a[0][0]+1)*j+(a[0][0]+2)*k+(a[0][0]+3)*l < w:
                    ans = max(ans, b[0][i]+b[1][j]+b[2][k]+b[3][l])
print(ans)

Submission status: Wrong Answer

Solution code:
n,w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [[] for _ in range(4)]
for i,j in a:
    b[i-a[0][0]].append(j)
#print(b)
if (a[0][0]>=500):
    x = w//a[0][0]
    y = w%a[0][0]
    z = b[0]+b[1]+b[2]+b[3]
    z.sort()
    z.reverse()
    if (y>3*n):
        print(sum(z[:x]))
    else:
        print(0)
        exit()
        dp = [[0]*(y+1) for _ in range(n+1)]
        for i in range(1,n+1):
            for j in range(0,y+1):
                if (j<(a[i-1][0]-a[0][0])):
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-a[i-1][0]+a[0][0]]+a[i-1][1])
        print(max(sum(z[:x-1]),dp[n][y]))
else:
    dp = [[0]*((a[0][0]+3)*n) for _ in range(n+1)]
    for i in range(1,n+1):
        #print(dp[i-1])
        for j in range(0,(a[0][0]+3)*n):
            if (j<a[i-1][0]):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i-1][0]]+a[i-1][1])
    #print(dp[n])
    if (w<(a[0][0]+3)*n):
        print(dp[n][w])
    else:
        print(dp[n][-1])