結果

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

ソースコード

diff # 

import sys
from sys import stdin

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.left = None
        self.right = None
        self.line = None
        self.l = l
        self.r = r
        self.m = (l + r) // 2

    def update(self, new_line):
        if self.line is None:
            self.line = new_line
            return
        current_val = self.line.get(self.m)
        new_val = new_line.get(self.m)
        if new_val > current_val:
            temp = self.line
            self.line = new_line
            new_line = temp
        current_l = self.line.get(self.l)
        new_l = new_line.get(self.l)
        if new_l > current_l:
            if not self.left:
                self.left = LiChaoNode(self.l, self.m)
            self.left.update(new_line)
        else:
            current_r = self.line.get(self.r)
            new_r = new_line.get(self.r)
            if new_r > current_r:
                if not self.right:
                    self.right = LiChaoNode(self.m + 1, self.r)
                self.right.update(new_line)

    def query(self, x):
        res = -float('inf')
        if self.line is not None:
            res = self.line.get(x)
        if x <= self.m:
            if self.left:
                left_res = self.left.query(x)
                res = max(res, left_res)
        else:
            if self.right:
                right_res = self.right.query(x)
                res = max(res, right_res)
        return res

class LiChaoTree:
    def __init__(self, L, R):
        self.root = LiChaoNode(L, R)

    def add_line(self, a, b):
        new_line = Line(a, b)
        self.root.update(new_line)

    def query(self, x):
        return self.root.query(x)

def main():
    n = int(stdin.readline())
    q = list(map(int, stdin.readline().split()))
    if n == 1:
        print(0)
        return
    L = -10**5
    R = 10**5
    tree = LiChaoTree(L, R)
    max_E = -float('inf')
    current = 0
    tree.add_line(q[0], current)
    for i in range(1, n):
        x = q[i]
        current = tree.query(x)
        if current > max_E:
            max_E = current
        a = q[i]
        tree.add_line(a, current)
    print(max_E)

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