Submission #8525778


Source Code Expand

import bisect
N,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(N)]
w1=wv[0][0]

Wlist=[0]+[j*w1+i for j in range(1,N+1) for i in range(3*j+1)]
Wlist=sorted(set(Wlist))
LW=len(Wlist)
dp=[[0]*LW for _ in range(N+1)]
#dp[i][j]:N個の物に対して強度(Wlist[j])のバッグ

for i in range(1,N+1):
  w,v=wv[i-1]
  for j in range(LW):
    if w<=Wlist[j]:      
      ind=bisect.bisect_right(Wlist,Wlist[j]-w)-1
      dp[i][j]=max(dp[i-1][j],dp[i-1][ind]+v)
    else:
      dp[i][j]=dp[i-1][j]

ind=bisect.bisect_right(Wlist,W)-1
print(dp[N][ind])

Submission Info

Submission Time
Task D - Simple Knapsack
User Wattawa
Language Python (3.4.3)
Score 400
Code Size 597 Byte
Status AC
Exec Time 1884 ms
Memory 59712 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 4
AC × 16
Set Name Test Cases
Sample example0, example1, example2, example3
All antigreedy0, antigreedy1, antigreedy2, example0, example1, example2, example3, quarter0, quarter1, quarter2, rand0, rand1, rand2, smallw0, smallw1, smallw2
Case Name Status Exec Time Memory
antigreedy0 AC 1883 ms 58704 KB
antigreedy1 AC 1884 ms 59084 KB
antigreedy2 AC 1801 ms 57192 KB
example0 AC 18 ms 3064 KB
example1 AC 17 ms 3064 KB
example2 AC 18 ms 3064 KB
example3 AC 18 ms 3064 KB
quarter0 AC 1031 ms 31524 KB
quarter1 AC 1138 ms 33932 KB
quarter2 AC 690 ms 22672 KB
rand0 AC 18 ms 3064 KB
rand1 AC 253 ms 10144 KB
rand2 AC 51 ms 4072 KB
smallw0 AC 1841 ms 58332 KB
smallw1 AC 1833 ms 59712 KB
smallw2 AC 347 ms 11836 KB