結果

問題 No.2458 Line Up Charged Balls
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:48:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,341 bytes
コンパイル時間 281 ms
コンパイル使用メモリ 82,972 KB
実行使用メモリ 143,900 KB
最終ジャッジ日時 2025-06-12 15:48:26
合計ジャッジ時間 4,735 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 1 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

class Line:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def get(self, a):
        return self.x * a + self.y

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, l, r):
        self.root = LiChaoNode(l, r)

    def insert(self, node, new_line):
        l = node.l
        r = node.r
        if node.line is None:
            node.line = new_line
            return
        mid = (l + r) / 2
        current_val = node.line.get(mid)
        new_val = new_line.get(mid)
        if new_val > current_val:
            temp = node.line
            node.line = new_line
            new_line = temp
        left_better = new_line.get(l) > node.line.get(l)
        right_better = new_line.get(r) > node.line.get(r)
        if left_better:
            if node.left is None:
                node.left = LiChaoNode(l, mid)
            self.insert(node.left, new_line)
        if right_better:
            if node.right is None:
                node.right = LiChaoNode(mid, r)
            self.insert(node.right, new_line)

    def query(self, node, a):
        if node is None:
            return -float('inf')
        current_val = node.line.get(a) if node.line is not None else -float('inf')
        mid = (node.l + node.r) / 2
        if a <= mid:
            child_val = self.query(node.left, a)
        else:
            child_val = self.query(node.right, a)
        return max(current_val, child_val)

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    q = list(map(int, input[idx:idx+n]))
    idx += n

    if n < 2:
        print(0)
        return

    li_chao = LiChaoTree(-10**5, 10**5)
    dp = [0] * n
    max_e = -float('inf')

    # Insert the first line
    new_line = Line(q[0], dp[0])
    li_chao.insert(li_chao.root, new_line)

    for i in range(1, n):
        a = q[i]
        current_max = li_chao.query(li_chao.root, a)
        dp[i] = current_max
        new_line = Line(q[i], dp[i])
        li_chao.insert(li_chao.root, new_line)
        if dp[i] > max_e:
            max_e = dp[i]

    print(max_e)

if __name__ == "__main__":
    main()
0