Submission #2531558


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 i in range(1,N+1):
        tot += D[i-1][0]
        for j in range(tot,D[i-1][0]-1,-1):
            if (dp[j] > dp[j-D[i-1][0]] + D[i-1][1] ):
                dp[j] = dp[j-D[i-1][0]] + D[i-1][1] 
    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 i in range(1,N+1):
        tot += D[i-1][1]
        for j in range(tot,D[i-1][1]-1,-1):
            if dp[j] < dp[j-D[i-1][1]] + D[i-1][0]:
                dp[j] = dp[j-D[i-1][1]] + D[i-1][0]
    value = max(dp[:min(W+1,200001)])
else:
    value =0
print(value)

Submission Info

Submission Time
Task D - ナップサック問題
User okumura
Language Python (3.4.3)
Score 0
Code Size 1148 Byte
Status WA
Exec Time 2104 ms
Memory 9292 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 0 / 34 0 / 33 0 / 33
Status
AC × 3
WA × 1
AC × 5
WA × 14
AC × 3
TLE × 14
AC × 3
TLE × 11
Set Name Test Cases
Sample subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask1 subtask01_0.txt, subtask01_1.txt, subtask01_10.txt, subtask01_11.txt, subtask01_12.txt, subtask01_13.txt, subtask01_14.txt, subtask01_2.txt, subtask01_3.txt, subtask01_4.txt, subtask01_5.txt, subtask01_6.txt, subtask01_7.txt, subtask01_8.txt, subtask01_9.txt, subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask2 subtask02_0.txt, subtask02_1.txt, subtask02_10.txt, subtask02_11.txt, subtask02_12.txt, subtask02_13.txt, subtask02_14.txt, subtask02_2.txt, subtask02_3.txt, subtask02_4.txt, subtask02_5.txt, subtask02_6.txt, subtask02_7.txt, subtask02_8.txt, subtask02_9.txt, subtask00_sample_1.txt, subtask00_sample_3.txt
Subtask3 subtask03_0.txt, subtask03_1.txt, subtask03_10.txt, subtask03_11.txt, subtask03_2.txt, subtask03_3.txt, subtask03_4.txt, subtask03_5.txt, subtask03_6.txt, subtask03_7.txt, subtask03_8.txt, subtask03_9.txt, subtask00_sample_1.txt, subtask00_sample_4.txt
Case Name Status Exec Time Memory
subtask00_sample_1.txt AC 33 ms 4724 KB
subtask00_sample_2.txt WA 18 ms 3188 KB
subtask00_sample_3.txt AC 24 ms 4724 KB
subtask00_sample_4.txt AC 38 ms 4724 KB
subtask01_0.txt WA 18 ms 3188 KB
subtask01_1.txt WA 18 ms 3188 KB
subtask01_10.txt WA 18 ms 3188 KB
subtask01_11.txt WA 18 ms 3188 KB
subtask01_12.txt WA 18 ms 3188 KB
subtask01_13.txt WA 18 ms 3188 KB
subtask01_14.txt WA 18 ms 3188 KB
subtask01_2.txt WA 18 ms 3188 KB
subtask01_3.txt WA 18 ms 3188 KB
subtask01_4.txt WA 18 ms 3188 KB
subtask01_5.txt AC 20 ms 4724 KB
subtask01_6.txt AC 33 ms 4724 KB
subtask01_7.txt WA 18 ms 3188 KB
subtask01_8.txt WA 18 ms 3188 KB
subtask01_9.txt WA 18 ms 3188 KB
subtask02_0.txt TLE 2104 ms 7372 KB
subtask02_1.txt TLE 2104 ms 8128 KB
subtask02_10.txt TLE 2104 ms 8000 KB
subtask02_11.txt TLE 2104 ms 8000 KB
subtask02_12.txt TLE 2104 ms 7748 KB
subtask02_13.txt AC 28 ms 4724 KB
subtask02_14.txt TLE 2104 ms 9292 KB
subtask02_2.txt TLE 2104 ms 8000 KB
subtask02_3.txt TLE 2104 ms 7748 KB
subtask02_4.txt TLE 2104 ms 8128 KB
subtask02_5.txt TLE 2104 ms 8284 KB
subtask02_6.txt TLE 2104 ms 7876 KB
subtask02_7.txt TLE 2104 ms 8000 KB
subtask02_8.txt TLE 2104 ms 7748 KB
subtask02_9.txt TLE 2104 ms 8000 KB
subtask03_0.txt TLE 2104 ms 4964 KB
subtask03_1.txt TLE 2104 ms 4980 KB
subtask03_10.txt TLE 2074 ms 5236 KB
subtask03_11.txt AC 40 ms 4724 KB
subtask03_2.txt TLE 2104 ms 4964 KB
subtask03_3.txt TLE 2096 ms 5604 KB
subtask03_4.txt TLE 2081 ms 5492 KB
subtask03_5.txt TLE 2059 ms 5364 KB
subtask03_6.txt TLE 2071 ms 5220 KB
subtask03_7.txt TLE 2104 ms 6900 KB
subtask03_8.txt TLE 2104 ms 6884 KB
subtask03_9.txt TLE 2104 ms 6900 KB