結果
問題 |
No.703 ゴミ拾い Easy
|
ユーザー |
![]() |
提出日時 | 2021-08-14 03:37:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 635 ms / 1,500 ms |
コード長 | 2,323 bytes |
コンパイル時間 | 149 ms |
コンパイル使用メモリ | 82,556 KB |
実行使用メモリ | 189,868 KB |
最終ジャッジ日時 | 2024-10-04 08:17:52 |
合計ジャッジ時間 | 14,943 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
ソースコード
import sys def I(): return int(sys.stdin.readline().rstrip()) def MI(): return map(int,sys.stdin.readline().rstrip().split()) def LI(): return list(map(int,sys.stdin.readline().rstrip().split())) def LI2(): return list(map(int,sys.stdin.readline().rstrip())) def S(): return sys.stdin.readline().rstrip() def LS(): return list(sys.stdin.readline().rstrip().split()) def LS2(): return list(sys.stdin.readline().rstrip()) class LiChao_tree(): def __init__(self,X): # Xに属する点における最小値を考える X = sorted(set(X)) self.inf = 1 << 61 self.N = 1 << (len(X)-1).bit_length() self.X = X+[self.inf]*(self.N-len(X)) self.tree = [None]*(self.N << 1) self.X_dict = {x: i for i,x in enumerate(X)} def get_val(self,a,b,x): return a*x+b def add_line(self,a,b): # 直線ax+bの追加 i = 1 left,right = 0,self.N while left < right: if self.tree[i] is None: self.tree[i] = (a,b) return mid = (left+right) >> 1 x_left,x_mid,x_right = self.X[left],self.X[mid],self.X[right-1] ai,bi = self.tree[i] comp_left = self.get_val(a,b,x_left) < self.get_val(ai,bi,x_left) comp_mid = self.get_val(a,b,x_mid) < self.get_val(ai,bi,x_mid) comp_right = self.get_val(a,b,x_right) < self.get_val(ai,bi,x_right) if comp_left == comp_right: if comp_left: self.tree[i] = (a,b) return if comp_mid: self.tree[i],a,b = (a,b),ai,bi if comp_left != comp_mid: i,right = i << 1,mid else: i,left = i << 1 | 1,mid def get_min(self,x): # xにおける最小値を返す i = self.X_dict[x]+self.N res = self.inf while i: if self.tree[i] is not None: a,b = self.tree[i] res = min(res,self.get_val(a,b,x)) i >>= 1 return res N = I() A = [0]+LI() X = [0]+LI() Y = [0]+LI() inf = 10**18 dp = [inf]*(N+1) dp[0] = 0 LCT = LiChao_tree(A[1:]) for i in range(1,N+1): x,y = X[i],Y[i] LCT.add_line(-2*x,x**2+y**2+dp[i-1]) a = A[i] dp[i] = a**2+LCT.get_min(a) ans = dp[-1] print(ans)