結果

問題 No.703 ゴミ拾い Easy
ユーザー toyuzukotoyuzuko
提出日時 2020-11-24 23:16:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 840 ms / 1,500 ms
コード長 2,294 bytes
コンパイル時間 551 ms
コンパイル使用メモリ 86,988 KB
実行使用メモリ 164,100 KB
最終ジャッジ日時 2023-10-01 01:18:17
合計ジャッジ時間 18,373 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
71,132 KB
testcase_01 AC 74 ms
71,360 KB
testcase_02 AC 73 ms
71,248 KB
testcase_03 AC 73 ms
71,408 KB
testcase_04 AC 74 ms
71,056 KB
testcase_05 AC 73 ms
71,288 KB
testcase_06 AC 77 ms
71,252 KB
testcase_07 AC 78 ms
71,196 KB
testcase_08 AC 74 ms
71,276 KB
testcase_09 AC 73 ms
71,404 KB
testcase_10 AC 74 ms
71,420 KB
testcase_11 AC 71 ms
71,364 KB
testcase_12 AC 73 ms
71,356 KB
testcase_13 AC 72 ms
71,400 KB
testcase_14 AC 112 ms
77,504 KB
testcase_15 AC 107 ms
77,616 KB
testcase_16 AC 107 ms
77,140 KB
testcase_17 AC 110 ms
77,648 KB
testcase_18 AC 110 ms
77,628 KB
testcase_19 AC 107 ms
77,484 KB
testcase_20 AC 105 ms
77,132 KB
testcase_21 AC 109 ms
77,432 KB
testcase_22 AC 109 ms
77,500 KB
testcase_23 AC 109 ms
77,428 KB
testcase_24 AC 732 ms
163,836 KB
testcase_25 AC 840 ms
163,640 KB
testcase_26 AC 688 ms
163,768 KB
testcase_27 AC 709 ms
163,756 KB
testcase_28 AC 675 ms
163,832 KB
testcase_29 AC 686 ms
163,464 KB
testcase_30 AC 668 ms
164,100 KB
testcase_31 AC 686 ms
163,892 KB
testcase_32 AC 681 ms
163,708 KB
testcase_33 AC 687 ms
164,072 KB
testcase_34 AC 284 ms
156,664 KB
testcase_35 AC 277 ms
156,544 KB
testcase_36 AC 276 ms
156,780 KB
testcase_37 AC 278 ms
156,644 KB
testcase_38 AC 279 ms
156,700 KB
testcase_39 AC 275 ms
156,532 KB
testcase_40 AC 280 ms
156,876 KB
testcase_41 AC 285 ms
156,996 KB
testcase_42 AC 284 ms
156,556 KB
testcase_43 AC 283 ms
156,604 KB
testcase_44 AC 74 ms
70,932 KB
testcase_45 AC 74 ms
71,352 KB
testcase_46 AC 270 ms
152,452 KB
testcase_47 AC 278 ms
152,384 KB
testcase_48 AC 110 ms
77,680 KB
testcase_49 AC 113 ms
77,496 KB
権限があれば一括ダウンロードができます

ソースコード

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