結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
![]() |
提出日時 | 2024-07-11 03:35:20 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 844 bytes |
コンパイル時間 | 308 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 77,312 KB |
最終ジャッジ日時 | 2024-07-11 03:35:25 |
合計ジャッジ時間 | 4,687 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 WA * 4 |
ソースコード
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)<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+=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)