結果

問題 No.1297 銅像
ユーザー Kiri8128Kiri8128
提出日時 2021-06-08 23:18:33
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,251 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 123,520 KB
最終ジャッジ日時 2024-05-05 10:24:05
合計ジャッジ時間 8,314 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
54,528 KB
testcase_01 AC 44 ms
54,400 KB
testcase_02 AC 46 ms
54,528 KB
testcase_03 AC 47 ms
54,272 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 130 ms
79,232 KB
testcase_08 WA -
testcase_09 AC 434 ms
123,264 KB
testcase_10 AC 347 ms
123,520 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 383 ms
123,136 KB
testcase_15 AC 405 ms
123,136 KB
testcase_16 AC 413 ms
123,392 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 357 ms
123,136 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
class 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 Query
    def __init__(self, X): # X: 調べる可能性のある x 座標のリスト
        X = sorted(list(set(X)))
        self.inf = 10 ** 18
        self.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] = f
                return
            cl = (fi[0] - f[0]) * l + fi[1] - f[1] > 0
            cr = (fi[0] - f[0]) * r + fi[1] - f[1] > 0
            
            if cl and cr:
                self.F[i] = f
                return
            if not cl and not cr:
                return
            if (fi[0] - f[0]) * m + fi[1] - f[1] > 0:
                self.F[i], f = f, fi
                cl = not cl
            if cl:
                i *= 2
            else:
                i = i * 2 + 1
    
    def query(self, x):
        i = self.D[x] + self.n
        mi = self.inf
        while i > 0:
            if self.F[i]:
                mi = min(mi, self.calc(self.F[i], x))
            i >>= 1
        return mi
    
    def add_line(self, a, b): # y = ax + b
        f = (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 sys
input = lambda: sys.stdin.readline().rstrip()
cht = CHT()
cht.add_line(0, 0)
N, C = map(int, input().split())
lct = LiChaoTree([i for i in range(N + 1)])
C *= 2
X = [0] * (N + 1) # i 番目の職人を使うときに i 番目の島までのコストの最小値
Y = [0] * (N + 1) # i 番目の島までのコストの最小値
for i in range(1, N + 1):
    a, b = map(int, input().split())
    a *= 2
    b *= 2
    z = cht.query(a + C * i) + b + i * a + C // 2 * (i ** 2 - i)
    X[i] = z
    lct.add_line(a - C // 2 * (2 * i - 1), X[i] - i * a + C // 2 * (i ** 2 - i))
    if i == -999:
        Y[i] = X[i]
    else:
        Y[i] = lct.query(i) + C // 2 * i ** 2
    
    cht.add_line(-i, (i ** 2 + i) * C // 2 + Y[i])
print(Y[-1] // 2)
0