Submission #2531774

---

Source Code Expand

from operator import itemgetter

N ,W = map(int,input().split())
DD=[]
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
    DD.append([v,w])

if (case_v ==0):#iこまで使った時に価値がjになる重さの最小値
    INF = 10**9 +1
    dp=[INF]*(200001)
    tot=0
    dp[0]=0
    D =sorted(DD, key = itemgetter(0)) 
    for x,y in D:
        for j in range(tot,-1,-1):
            if (dp[j+x] > dp[j] + y ):
                dp[j+x] = dp[j] + y
        tot += x
    value = max([j for j in range(200001) if dp[j] <= W])
elif(case_w == 0):#iこまで使った時に重さがjになる価値の最大値
    dp=[0]*(200001) 
    tot=0
    D =sorted(DD, key = itemgetter(1)) 
    for x,y in D:
        for j in range(tot,-1,-1):
            if dp[j+y] < dp[j] + x:
                dp[j+y] = dp[j] + x
        tot += y
    value = max(dp[:min(W+1,200001)])
else:
    value =0
print(value)

Submission Info

Judge Result