結果
問題 | No.1297 銅像 |
ユーザー |
![]() |
提出日時 | 2021-06-08 23:38:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 632 ms / 2,000 ms |
コード長 | 3,308 bytes |
コンパイル時間 | 167 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 175,056 KB |
最終ジャッジ日時 | 2024-11-27 06:52:00 |
合計ジャッジ時間 | 10,208 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
from collections import dequeclass CHT(): # Convex Hull Trick, Sorted Lines, Sorted Queries, Min Query# add_line は a の降順# query は x の昇順def __init__(self):self.Q = deque()def calc(self, f, x):return f[0] * x + f[1]def check(self, f1, f2, f3):return (f2[0] - f1[0]) * (f3[1] - f2[1]) >= (f2[1] - f1[1]) * (f3[0] - f2[0])def add_line(self, a, b):f = (a, b)while len(self.Q) >= 2 and self.check(self.Q[-2], self.Q[-1], f):self.Q.pop()self.Q.append(f)def query(self, x):while len(self.Q) >= 2 and self.calc(self.Q[0], x) >= self.calc(self.Q[1], x):self.Q.popleft()return self.calc(self.Q[0], x)class LiChaoTree:# Min Querydef __init__(self, X): # X: 調べる可能性のある x 座標のリストX = sorted(list(set(X)))self.inf = 10 ** 18self.n = 1 << (len(X) - 1).bit_length()self.X = X + [self.inf] * (self.n - len(X))self.D = {a: i for i, a in enumerate(X)}self.lmr = [(0, 0, 0)] * self.n + [(x, x, x) for x in self.X]for i in range(1, self.n)[::-1]:self.lmr[i] = (self.lmr[i*2][0], self.lmr[i*2][2], self.lmr[i*2^1][2])self.F = [None] * (self.n * 2)def calc(self, f, x):return f[0] * x + f[1]def update(self, i, f):while 1:l, m, r = self.lmr[i]fi = self.F[i]if fi is None:self.F[i] = freturncl = (fi[0] - f[0]) * l + fi[1] - f[1] > 0cr = (fi[0] - f[0]) * r + fi[1] - f[1] > 0if cl and cr:self.F[i] = freturnif not cl and not cr:returnif (fi[0] - f[0]) * m + fi[1] - f[1] > 0:self.F[i], f = f, ficl = not clif cl:i *= 2else:i = i * 2 + 1def query(self, x):i = self.D[x] + self.nmi = self.infwhile i > 0:if self.F[i]:mi = min(mi, self.calc(self.F[i], x))i >>= 1return midef add_line(self, a, b): # y = ax + bf = (a, b)self.update(1, f)def debug(self):print("F =", self.F)print("X =", self.X)print("D =", self.D)print("lmr =", self.lmr)import sysinput = lambda: sys.stdin.readline().rstrip()N, C = map(int, input().split())lct1 = LiChaoTree([i for i in range(N + 1)])C *= 2X = [0] * (N + 1) # i 番目の職人を使うときに i 番目の島までのコストの最小値Y = [0] * (N + 1) # i 番目の島までのコストの最小値I = []Z = []for i in range(1, N + 1):a, b = map(int, input().split())a *= 2b *= 2I.append((a, b))Z.append(a + C * i)lct2 = LiChaoTree(Z)lct2.add_line(0, 0)for i, (a, b) in enumerate(I, 1):z = lct2.query(a + C * i) + b + i * a + C // 2 * (i ** 2 - i)X[i] = zlct1.add_line(a - C // 2 * (2 * i - 1), X[i] - i * a + C // 2 * (i ** 2 - i))Y[i] = lct1.query(i) + C // 2 * i ** 2lct2.add_line(-i, (i ** 2 + i) * C // 2 + Y[i])print(Y[-1] // 2)