結果

問題 No.2458 Line Up Charged Balls
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:49:26
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,524 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 81,864 KB
実行使用メモリ 148,112 KB
最終ジャッジ日時 2025-04-15 22:51:43
合計ジャッジ時間 4,701 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 10 TLE * 4 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

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

    def get(self, x):
        return self.a * 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.root = LiChaoNode(x_min, x_max)

    def insert(self, node, new_line):
        if node is None:
            return
        l = node.l
        r = node.r
        m = (l + r) // 2
        if node.line is None:
            node.line = new_line
            return
        current_val = node.line.get(m)
        new_val = new_line.get(m)
        if new_val > current_val:
            node.line, new_line = new_line, node.line
        current_val_l = node.line.get(l)
        new_val_l = new_line.get(l)
        if new_val_l > current_val_l:
            if l < r:
                if not node.left:
                    node.left = LiChaoNode(l, m)
                self.insert(node.left, new_line)
        current_val_r = node.line.get(r)
        new_val_r = new_line.get(r)
        if new_val_r > current_val_r:
            if l < r:
                if not node.right:
                    node.right = LiChaoNode(m + 1, r)
                self.insert(node.right, new_line)

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

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    Q = list(map(int, input[1:N+1]))
    if N < 2:
        print(0)
        return
    x_min = -10**5
    x_max = 10**5
    lichao = LiChaoTree(x_min, x_max)
    dp = [0] * N
    for i in range(N):
        if i == 0:
            continue
        elif i == 1:
            dp[i] = Q[0] * Q[1]
            line = Line(Q[i], dp[i])
            lichao.insert(lichao.root, line)
        else:
            x = Q[i]
            current_max = lichao.query(lichao.root, x)
            dp[i] = current_max
            line = Line(Q[i], dp[i])
            lichao.insert(lichao.root, line)
    max_e = max(dp[1:])
    print(max_e)

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