結果
問題 | No.703 ゴミ拾い Easy |
ユーザー |
|
提出日時 | 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 |
ソースコード
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.logself.ele = (0, INF)self.xs = x_list + [INF] * (self.n - len(x_list))self.inf = INFself.tree = [self.ele for _ in range(2 * self.n)]def f(self, line, x):a, b = linereturn a * x + bdef _add_(self, line, ind, left, right):while True:mid = (left + right) // 2lx = 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] = linereturnif not lu and not ru:returnif mu:self.tree[ind], line = line, self.tree[ind]if lu != mu:right = midind = ind * 2else:left = midind = ind * 2 + 1def 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.nleft, right = self.comp[left], self.comp[right]size = 1while lind < rind:if lind & 1:self._add_(line, lind, left, left + size)lind += 1left += sizeif rind & 1:rind -= 1right -= sizeself._add_(line, rind, right, right + size)lind >>= 1rind >>= 1size <<= 1def get_min(self, x):ind = self.comp[x] + self.nres = self.infwhile ind:res = min(res, self.f(self.tree[ind], x))ind >>= 1return resn = 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] = 0LCT = 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] ** 2print(dp[-1])