結果
問題 |
No.626 Randomized 01 Knapsack
|
ユーザー |
![]() |
提出日時 | 2024-07-11 03:42:25 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,065 bytes |
コンパイル時間 | 369 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 104,320 KB |
最終ジャッジ日時 | 2024-07-11 03:42:32 |
合計ジャッジ時間 | 7,224 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 11 TLE * 1 -- * 13 |
ソースコード
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)) MMAX=0 for tests in range(25,1000,25): if len(LASTS)<tests: Q=[(0,0)] first=-1 ANS=0 M=M0 else: first,ANS,M=LASTS[-tests] 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) if MAX!=MMAX: MMAX=MAX else: break print(ANS+MMAX)