結果
問題 | No.817 Coin donation |
ユーザー |
👑 ![]() |
提出日時 | 2021-02-10 17:54:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 110 ms / 2,000 ms |
コード長 | 1,299 bytes |
コンパイル時間 | 165 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 83,456 KB |
最終ジャッジ日時 | 2024-07-08 04:24:01 |
合計ジャッジ時間 | 2,119 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 14 |
ソースコード
def General_Binary_Increase_Search(L,R,cond,Integer=True,ep=1/(1<<20),Times=50):"""条件式が単調増加であるとき,一般的な二部探索を行う.L:解の下限R:解の上限cond:条件(1変数関数,広義単調減少 or 広義単調減少を満たす)Integer:解を整数に制限するか?ep:Integer=Falseのとき,解の許容する誤差"""if not(cond(R)):return Noneif cond(L):return Lif Integer:R+=1while R-L>1:C=L+(R-L)//2if cond(C):R=Celse:L=Creturn Relse:while (R-L)>=ep and Times:Times-=1C=L+(R-L)/2if cond(C):R=Celse:L=Creturn R#================================================def check(x):M=0for i in range(N):M+=max(0,min(Y[i],x)-X[i]+1)return M>=K#================================================import sysinput=sys.stdin.readlineN,K=map(int,input().split())X=[]X_append=X.appendY=[]Y_append=Y.appendSum=0for _ in range(N):a,b=map(int,input().split())X_append(a)Y_append(b)Sum+=b-a+1print(General_Binary_Increase_Search(0,10**10,check))