結果

問題 No.703 ゴミ拾い Easy
ユーザー NatsubiSoganNatsubiSogan
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
52,352 KB
testcase_01 AC 42 ms
52,096 KB
testcase_02 AC 39 ms
52,352 KB
testcase_03 AC 39 ms
52,608 KB
testcase_04 AC 38 ms
52,736 KB
testcase_05 AC 39 ms
52,736 KB
testcase_06 AC 38 ms
52,608 KB
testcase_07 AC 39 ms
52,864 KB
testcase_08 AC 39 ms
52,608 KB
testcase_09 AC 38 ms
52,096 KB
testcase_10 AC 38 ms
52,096 KB
testcase_11 AC 38 ms
52,736 KB
testcase_12 AC 38 ms
52,352 KB
testcase_13 AC 39 ms
52,096 KB
testcase_14 AC 81 ms
76,160 KB
testcase_15 AC 88 ms
76,032 KB
testcase_16 AC 91 ms
76,412 KB
testcase_17 AC 85 ms
76,788 KB
testcase_18 AC 81 ms
76,416 KB
testcase_19 AC 79 ms
76,416 KB
testcase_20 AC 76 ms
76,416 KB
testcase_21 AC 84 ms
76,288 KB
testcase_22 AC 83 ms
76,288 KB
testcase_23 AC 85 ms
76,392 KB
testcase_24 AC 577 ms
182,812 KB
testcase_25 AC 570 ms
182,684 KB
testcase_26 AC 592 ms
182,804 KB
testcase_27 AC 573 ms
182,680 KB
testcase_28 AC 539 ms
182,672 KB
testcase_29 AC 565 ms
182,316 KB
testcase_30 AC 559 ms
182,808 KB
testcase_31 AC 558 ms
183,308 KB
testcase_32 AC 527 ms
183,060 KB
testcase_33 AC 561 ms
182,812 KB
testcase_34 AC 256 ms
164,176 KB
testcase_35 AC 246 ms
163,652 KB
testcase_36 AC 244 ms
163,572 KB
testcase_37 AC 241 ms
163,816 KB
testcase_38 AC 239 ms
163,700 KB
testcase_39 AC 245 ms
164,076 KB
testcase_40 AC 242 ms
163,468 KB
testcase_41 AC 243 ms
164,132 KB
testcase_42 AC 241 ms
163,740 KB
testcase_43 AC 252 ms
163,824 KB
testcase_44 AC 39 ms
52,096 KB
testcase_45 AC 39 ms
52,480 KB
testcase_46 AC 253 ms
164,788 KB
testcase_47 AC 255 ms
160,392 KB
testcase_48 AC 86 ms
76,456 KB
testcase_49 AC 85 ms
76,288 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