結果

問題 No.703 ゴミ拾い Easy
ユーザー NatsubiSoganNatsubiSogan
提出日時 2021-02-13 01:51:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 573 ms / 1,500 ms
コード長 2,448 bytes
コンパイル時間 1,212 ms
コンパイル使用メモリ 86,964 KB
実行使用メモリ 188,492 KB
最終ジャッジ日時 2023-09-27 09:08:22
合計ジャッジ時間 17,573 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 62 ms
71,416 KB
testcase_01 AC 62 ms
71,496 KB
testcase_02 AC 65 ms
71,508 KB
testcase_03 AC 66 ms
71,300 KB
testcase_04 AC 65 ms
71,272 KB
testcase_05 AC 64 ms
71,492 KB
testcase_06 AC 65 ms
71,372 KB
testcase_07 AC 63 ms
71,304 KB
testcase_08 AC 62 ms
71,308 KB
testcase_09 AC 63 ms
71,368 KB
testcase_10 AC 64 ms
71,460 KB
testcase_11 AC 63 ms
71,304 KB
testcase_12 AC 65 ms
71,232 KB
testcase_13 AC 64 ms
71,440 KB
testcase_14 AC 100 ms
77,476 KB
testcase_15 AC 95 ms
77,632 KB
testcase_16 AC 95 ms
77,616 KB
testcase_17 AC 97 ms
77,372 KB
testcase_18 AC 93 ms
77,468 KB
testcase_19 AC 95 ms
77,380 KB
testcase_20 AC 91 ms
77,216 KB
testcase_21 AC 109 ms
77,900 KB
testcase_22 AC 101 ms
77,480 KB
testcase_23 AC 98 ms
77,636 KB
testcase_24 AC 557 ms
188,140 KB
testcase_25 AC 554 ms
188,224 KB
testcase_26 AC 565 ms
188,344 KB
testcase_27 AC 573 ms
187,976 KB
testcase_28 AC 544 ms
188,344 KB
testcase_29 AC 556 ms
188,108 KB
testcase_30 AC 548 ms
188,124 KB
testcase_31 AC 551 ms
188,492 KB
testcase_32 AC 551 ms
188,352 KB
testcase_33 AC 565 ms
188,284 KB
testcase_34 AC 252 ms
162,828 KB
testcase_35 AC 249 ms
162,764 KB
testcase_36 AC 246 ms
162,924 KB
testcase_37 AC 247 ms
162,908 KB
testcase_38 AC 247 ms
162,728 KB
testcase_39 AC 240 ms
162,892 KB
testcase_40 AC 245 ms
162,924 KB
testcase_41 AC 253 ms
162,784 KB
testcase_42 AC 252 ms
162,924 KB
testcase_43 AC 250 ms
162,764 KB
testcase_44 AC 61 ms
71,552 KB
testcase_45 AC 64 ms
71,128 KB
testcase_46 AC 244 ms
167,592 KB
testcase_47 AC 248 ms
167,012 KB
testcase_48 AC 93 ms
77,492 KB
testcase_49 AC 93 ms
77,452 KB
権限があれば一括ダウンロードができます

ソースコード

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