結果
問題 | No.1767 BLUE to RED |
ユーザー |
👑 ![]() |
提出日時 | 2021-11-26 22:50:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 263 ms / 2,000 ms |
コード長 | 1,206 bytes |
コンパイル時間 | 143 ms |
コンパイル使用メモリ | 81,904 KB |
実行使用メモリ | 140,420 KB |
最終ジャッジ日時 | 2024-06-29 18:20:21 |
合計ジャッジ時間 | 5,055 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
def Binary_Search_Small_Count(A,x,equal=False,sort=False): """2分探索によって,x未満の要素の個数を調べる. A:リスト x:調べる要素 sort:ソートをする必要があるかどうか(Trueで必要) equal:Trueのときはx"未満"がx"以下"になる """ if sort: A.sort() if len(A)==0 or A[0]>x or ((not equal) and A[0]==x): return 0 L,R=0,len(A) while R-L>1: C=L+(R-L)//2 if A[C]<x or (equal and A[C]==x): L=C else: R=C return L+1 #================================================== N,M=map(int,input().split()) A=list(map(int,input().split())) B=list(map(int,input().split())) inf=float("inf") M=[[] for _ in range(N+1)] for i in range(N+1): if i==0: M[0]=[A[0]] elif i==N: M[N]=[A[N-1]] else: M[i]=[A[i-1],A[i]] for b in B: k=Binary_Search_Small_Count(A,b) M[k].append(b) X=0 for k in range(N+1): if k==0 or k==N: X+=max(M[k])-min(M[k]) continue if len(M[k])==2: continue M[k].sort() alpha=0 for j in range(len(M[k])-1): alpha=max(alpha,M[k][j+1]-M[k][j]) X+=(M[k][-1]-M[k][0])-alpha print(X)