結果

問題 No.1297 銅像
ユーザー Kiri8128Kiri8128
提出日時 2021-06-08 23:38:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 697 ms / 2,000 ms
コード長 3,308 bytes
コンパイル時間 1,385 ms
コンパイル使用メモリ 87,080 KB
実行使用メモリ 173,612 KB
最終ジャッジ日時 2023-08-18 04:13:50
合計ジャッジ時間 12,555 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 91 ms
71,624 KB
testcase_01 AC 93 ms
71,576 KB
testcase_02 AC 91 ms
71,636 KB
testcase_03 AC 93 ms
71,576 KB
testcase_04 AC 103 ms
76,904 KB
testcase_05 AC 100 ms
76,360 KB
testcase_06 AC 201 ms
82,752 KB
testcase_07 AC 185 ms
82,896 KB
testcase_08 AC 208 ms
82,884 KB
testcase_09 AC 643 ms
170,312 KB
testcase_10 AC 544 ms
159,068 KB
testcase_11 AC 660 ms
170,904 KB
testcase_12 AC 667 ms
173,612 KB
testcase_13 AC 665 ms
155,192 KB
testcase_14 AC 636 ms
154,500 KB
testcase_15 AC 586 ms
155,172 KB
testcase_16 AC 604 ms
149,528 KB
testcase_17 AC 676 ms
150,852 KB
testcase_18 AC 667 ms
157,240 KB
testcase_19 AC 619 ms
153,144 KB
testcase_20 AC 655 ms
170,776 KB
testcase_21 AC 697 ms
170,960 KB
testcase_22 AC 677 ms
155,848 KB
権限があれば一括ダウンロードができます

ソースコード

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()
N, C = map(int, input().split())
lct1 = LiChaoTree([i for i in range(N + 1)])
C *= 2
X = [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 *= 2
    b *= 2
    I.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] = z
    lct1.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 ** 2
    
    lct2.add_line(-i, (i ** 2 + i) * C // 2 + Y[i])
print(Y[-1] // 2)
0