結果
問題 |
No.626 Randomized 01 Knapsack
|
ユーザー |
![]() |
提出日時 | 2024-07-11 03:36:51 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 846 bytes |
コンパイル時間 | 382 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 82,304 KB |
最終ジャッジ日時 | 2024-07-11 03:37:02 |
合計ジャッジ時間 | 10,422 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 WA * 1 |
ソースコード
import sys input = sys.stdin.readline from operator import itemgetter N,M=map(int,input().split()) X=[list(map(int,input().split())) for i in range(N)] M0=M X.sort(reverse=True) X.sort(key=lambda x:x[0]/x[1],reverse=True) ANS=0 LASTS=[] for i in range(len(X)): v,w=X[i] if w<=M: ANS+=v M-=w LASTS.append((i,ANS,M)) if len(LASTS)<25: Q=[(0,0)] first=-1 ANS=0 M=M0 else: first,ANS,M=LASTS[-25] 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+=NQ Q.sort(key=itemgetter(1)) Q2=[] for x,y in Q: if Q2 and Q2[-1][0]>=x: continue else: Q2.append((x,y)) Q=Q2 MAX=0 for x,y in Q: MAX=max(MAX,x) print(ANS+MAX)