結果

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

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

class Line:
    def __init__(self, a, b):
        self.a = a  # slope
        self.b = b  # intercept

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

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

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

    def insert(self, node, new_line):
        if node.line is None:
            node.line = new_line
            return
        m = (node.l + node.r) // 2
        curr_val = node.line.get(m)
        new_val = new_line.get(m)
        if new_val > curr_val:
            # Swap the lines
            node.line, new_line = new_line, node.line
        # Check if new_line is better in the left child
        if new_line.get(node.l) > node.line.get(node.l):
            if node.left is None:
                node.left = LiChaoNode(node.l, m)
            self.insert(node.left, new_line)
        # Check if new_line is better in the right child
        if new_line.get(node.r) > node.line.get(node.r):
            if node.right is None:
                node.right = LiChaoNode(m, node.r)
            self.insert(node.right, new_line)

    def query(self, node, x):
        if node is None or node.line is None:
            return -float('inf')
        res = node.line.get(x)
        m = (node.l + node.r) // 2
        if x < m:
            left_res = self.query(node.left, x)
            res = max(res, left_res)
        else:
            right_res = self.query(node.right, x)
            res = max(res, right_res)
        return res

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    Q = list(map(int, data[1:N+1]))
    if N < 2:
        print(0)
        return
    x_min = -10**5
    x_max = 10**5 + 1
    tree = LiChaoTree(x_min, x_max)
    max_ans = -float('inf')
    for i in range(N):
        if i == 0:
            current_dp = 0
        else:
            x = Q[i]
            current_dp = tree.query(tree.root, x)
            if current_dp > max_ans:
                max_ans = current_dp
        new_line = Line(Q[i], current_dp)
        tree.insert(tree.root, new_line)
    print(max_ans if max_ans != -float('inf') else 0)

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