結果

問題 No.703 ゴミ拾い Easy
ユーザー toyuzukotoyuzuko
提出日時 2020-11-24 23:16:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 630 ms / 1,500 ms
コード長 2,294 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 81,780 KB
実行使用メモリ 179,708 KB
最終ジャッジ日時 2024-07-23 18:53:04
合計ジャッジ時間 15,760 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

INF = (1 << 63) - 1

class ConvexHullTrick():
    def __init__(self, xs):
        xs = sorted(set(xs))
        self.n = len(xs)
        self.cx = {x : k for k, x in enumerate(xs)}
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.e = (0, INF)
        self.x = xs + [INF] * (self.size - self.n)
        self.d = [self.e]  * (2 * self.size)

    def val(self, line, x):
        a, b = line
        return a * x + b

    def _add_(self, line, p, lt, rt):
        while True:
            md = (lt + rt) // 2
            lx = self.x[lt]
            mx = self.x[md]
            rx = self.x[rt - 1]
            lu = self.val(line, lx) < self.val(self.d[p], lx)
            mu = self.val(line, mx) < self.val(self.d[p], mx)
            ru = self.val(line, rx) < self.val(self.d[p], rx)
            if lu and ru:
                self.d[p] = line
                return
            if not lu and not ru:
                return
            if mu:
                self.d[p], line = line, self.d[p]
            if lu != mu:
                rt = md
                p = 2 * p
            else:
                lt = md
                p = 2 * p + 1

    def add_line(self, line):
        self._add_(line, 1, 0, self.size)

    def add_seg(self, line, lt, rt):
        lx = self.cx[lt] + self.size
        rx = self.cx[rt] + self.size
        lt = self.cx[lt]
        rt = self.cx[rt]
        sz = 1
        while lx < rx:
            if lx & 1:
                self._add_(line, lx, lt, lt + sz)
                lx += 1
                lt += sz
            if rx & 1:
                rx -= 1
                rt -= sz
                self._add_(line, rx, rt, rt + sz)
            lx >>= 1
            rx >>= 1
            sz <<= 1

    def get_min(self, x):
        p = self.cx[x] + self.size
        res = INF
        while p:
            res = min(res, self.val(self.d[p], x))
            p >>= 1
        return res

import sys
input = sys.stdin.buffer.readline

N = int(input())
A = list(map(int, input().split()))
X = list(map(int, input().split()))
Y = list(map(int, input().split()))

cht = ConvexHullTrick(A)

dp = [0] * (N + 1)

for i in range(N):
    cht.add_line((-2 * X[i], dp[i] + X[i]**2 + Y[i]**2))
    dp[i + 1] = cht.get_min(A[i]) + A[i]**2

print(dp[N])
0