結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
![]() |
提出日時 | 2024-07-11 03:55:19 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 808 bytes |
コンパイル時間 | 349 ms |
コンパイル使用メモリ | 82,312 KB |
実行使用メモリ | 87,784 KB |
最終ジャッジ日時 | 2024-07-11 03:55:28 |
合計ジャッジ時間 | 8,786 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 11 TLE * 2 -- * 12 |
ソースコード
import sysinput = sys.stdin.readlinefrom operator import itemgetterfrom bisect import bisectN,M=map(int,input().split())X=[list(map(int,input().split())) for i in range(N)]M0=MX.sort(key=lambda x:x[0]/x[1],reverse=True)ANS=0LASTS=[]for i in range(len(X)):v,w=X[i]if w<=M:ANS+=vM-=wLASTS.append((i,ANS,M))if len(LASTS)<75:Q=[(0,0)]first=-1ANS=0M=M0else:first,ANS,M=LASTS[-75]Q=[(0,0)]for i in range(first+1,len(X)):v,w=X[i]NQ=[]for x,y in Q:if w+x<=M:bx=bisect(Q,(w+x,1<<60))if Q[bx-1][1]<v+y:NQ.append((w+x,v+y))#print(Q,v,w)Q+=NQQ.sort(key=itemgetter(0))MAX=0for x,y in Q:MAX=max(MAX,y)print(ANS+MAX)