結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
![]() |
提出日時 | 2024-07-11 03:31:55 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 637 bytes |
コンパイル時間 | 394 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 104,048 KB |
最終ジャッジ日時 | 2024-07-11 03:32:13 |
合計ジャッジ時間 | 7,756 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 6 TLE * 2 -- * 17 |
ソースコード
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)<7:Q=[(0,0)]first=-1ANS=0M=M0else:first,ANS,M=LASTS[-7]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)