結果

問題 No.2458 Line Up Charged Balls
ユーザー lam6er
提出日時 2025-04-15 22:49:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,218 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 82,260 KB
実行使用メモリ 123,060 KB
最終ジャッジ日時 2025-04-15 22:51:15
合計ジャッジ時間 7,973 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Line:
    def __init__(self, m, b):
        self.m = m
        self.b = b

    def get(self, x):
        return self.m * x + self.b

class LiChaoNode:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.left = None
        self.right = None
        self.line = None

class LiChaoTree:
    def __init__(self, x_min, x_max):
        self.x_min = x_min
        self.x_max = x_max
        self.root = LiChaoNode(x_min, x_max)

    def insert_line(self, new_line):
        stack = [self.root]
        while stack:
            node = stack.pop()
            if node.line is None:
                node.line = new_line
                continue
            m = (node.l + node.r) // 2
            curr_val = node.line.get(m)
            new_val = new_line.get(m)
            if new_val > curr_val:
                node.line, new_line = new_line, node.line
            # Check left
            if new_line.get(node.l) > node.line.get(node.l):
                if not node.left:
                    node.left = LiChaoNode(node.l, m)
                stack.append(node.left)
            elif new_line.get(node.r) > node.line.get(node.r):
                if not node.right:
                    node.right = LiChaoNode(m+1, node.r)
                stack.append(node.right)

    def query(self, x):
        res = -float('inf')
        stack = [self.root]
        while stack:
            node = stack.pop()
            if not node:
                continue
            if node.line:
                res = max(res, node.line.get(x))
            m = (node.l + node.r) // 2
            if x <= m:
                if node.left:
                    stack.append(node.left)
            else:
                if node.right:
                    stack.append(node.right)
        return res

n = int(input())
Q = list(map(int, input().split()))
if n == 1:
    print(0)
else:
    x_min = -10**5
    x_max = 10**5
    tree = LiChaoTree(x_min, x_max)
    tree.insert_line(Line(Q[0], 0))
    max_E = -float('inf')
    for i in range(1, n):
        x = Q[i]
        current_E = tree.query(x)
        if current_E > max_E:
            max_E = current_E
        tree.insert_line(Line(Q[i], current_E))
    print(max_E)
0