結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
![]() |
提出日時 | 2024-07-11 03:09:17 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 448 bytes |
コンパイル時間 | 503 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 69,632 KB |
最終ジャッジ日時 | 2024-07-11 03:09:21 |
合計ジャッジ時間 | 3,993 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 WA * 18 |
ソースコード
import sysinput = sys.stdin.readlineN,M=map(int,input().split())X=[list(map(int,input().split())) for i in range(N)]X.sort(reverse=True)X.sort(key=lambda x:x[0]/x[1],reverse=True)Y=X[:-20]REST=X[-20:]ANS=0for v,w in Y:if w<=M:ANS+=vM-=wQ=[(0,0)]for v,w in REST: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)