結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
![]() |
提出日時 | 2024-07-11 03:30:58 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 638 bytes |
コンパイル時間 | 1,008 ms |
コンパイル使用メモリ | 82,276 KB |
実行使用メモリ | 551,228 KB |
最終ジャッジ日時 | 2024-07-11 03:31:04 |
合計ジャッジ時間 | 5,262 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 WA * 4 MLE * 1 -- * 18 |
ソースコード
import sysinput = sys.stdin.readlineN,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)<10:Q=[(0,0)]first=0ANS=0M=M0else:first,ANS,M=LASTS[-10]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+=NQMAX=0for x,y in Q:MAX=max(MAX,x)print(ANS+MAX)