結果

問題 No.703 ゴミ拾い Easy
ユーザー NatsubiSogan
提出日時 2021-02-13 01:51:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 592 ms / 1,500 ms
コード長 2,448 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 183,308 KB
最終ジャッジ日時 2024-07-20 03:15:43
合計ジャッジ時間 14,380 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class LiChaoTree:
def __init__(self, x_list, INF = 10 ** 18):
x_list = sorted(list(set(x_list)))
self.comp = {x : k for k, x in enumerate(x_list)}
self.log = (len(x_list) - 1).bit_length()
self.n = 1 << self.log
self.ele = (0, INF)
self.xs = x_list + [INF] * (self.n - len(x_list))
self.inf = INF
self.tree = [self.ele for _ in range(2 * self.n)]
def f(self, line, x):
a, b = line
return a * x + b
def _add_(self, line, ind, left, right):
while True:
mid = (left + right) // 2
lx = self.xs[left]
mx = self.xs[mid]
rx = self.xs[right - 1]
lu = self.f(line, lx) < self.f(self.tree[ind], lx)
mu = self.f(line, mx) < self.f(self.tree[ind], mx)
ru = self.f(line, rx) < self.f(self.tree[ind], rx)
if lu and ru:
self.tree[ind] = line
return
if not lu and not ru:
return
if mu:
self.tree[ind], line = line, self.tree[ind]
if lu != mu:
right = mid
ind = ind * 2
else:
left = mid
ind = ind * 2 + 1
def add_line(self, line):
self._add_(line, 1, 0, self.n)
def add_segment(self, line, left, right):
lind, rind = self.comp[left] + self.n, self.comp[right] + self.n
left, right = self.comp[left], self.comp[right]
size = 1
while lind < rind:
if lind & 1:
self._add_(line, lind, left, left + size)
lind += 1
left += size
if rind & 1:
rind -= 1
right -= size
self._add_(line, rind, right, right + size)
lind >>= 1
rind >>= 1
size <<= 1
def get_min(self, x):
ind = self.comp[x] + self.n
res = self.inf
while ind:
res = min(res, self.f(self.tree[ind], x))
ind >>= 1
return res
n = int(input())
a = list(map(int, input().split()))
x = list(map(int, input().split()))
y = list(map(int, input().split()))
dp = [10 ** 18] * (n + 1)
dp[0] = 0
LCT = LiChaoTree(a)
for i in range(1, n + 1):
LCT.add_line((-2 * x[i - 1], x[i - 1] ** 2 + y[i - 1] ** 2 + dp[i - 1]))
dp[i] = LCT.get_min(a[i - 1]) + a[i - 1] ** 2
print(dp[-1])
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0