Submission #2531278

---

Source Code Expand

from collections import deque
N ,W = map(int,input().split())
D=[]
case_v = 0
case_w = 0
for i in range(N):
    v,w = map(int,input().split())
    if (v > 1000):
        case_v = 1
    if (w>1000):
        case_w=1
    D.append([v,w])
if (case_v ==0):#iこまで使った時に価値がjになる重さの最小値
    dp=[10**9 +1]*(200001)
    dp[0]=0
    tot=0
    value = 0
    for i in range(1,N+1):
        tot += D[i-1][0]
        for j in range(tot,D[i-1][0]-1,-1):
            dp[j] = min(dp[j],dp[j-D[i-1][0]] + D[i-1][1])
            if dp[j] < W+1:
                value = max(value,j)
elif(case_w == 0):#iこまで使った時に重さがjになる価値の最大値
    dp=[[0]*(200001) for i in range(N+1)]
    tot=0
    value = 0
    for i in range(1,N+1):
        tot += D[i-1][1]
        for j in range(tot,D[i-1][1]-1,-1):
            dp[i][j] = max(dp[j],dp[j-D[i-1][1]] + D[i-1][0])
            if j <=W:
                value = max(value,dp[j])
else:
    value =0
print(value)

Submission Info

Judge Result