結果

問題 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])
0