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