結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
![]() |
提出日時 | 2024-07-11 03:40:04 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 846 bytes |
コンパイル時間 | 387 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 19,360 KB |
最終ジャッジ日時 | 2024-07-11 03:40:12 |
合計ジャッジ時間 | 7,828 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 11 TLE * 1 -- * 13 |
ソースコード
import sysinput = sys.stdin.readlinefrom operator import itemgetterN,M=map(int,input().split())X=[list(map(int,input().split())) for i in range(N)]M0=MX.sort(reverse=True)X.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)<80:Q=[(0,0)]first=-1ANS=0M=M0else:first,ANS,M=LASTS[-80]Q=[(0,0)]for i in range(first+1,len(X)):v,w=X[i]NQ=[]for x,y in Q:if w+y<=M:NQ.append((v+x,w+y))Q+=NQQ.sort(key=itemgetter(1))Q2=[]for x,y in Q:if Q2 and Q2[-1][0]>=x:continueelse:Q2.append((x,y))Q=Q2MAX=0for x,y in Q:MAX=max(MAX,x)print(ANS+MAX)