結果

問題 No.2458 Line Up Charged Balls
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:49:47
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,147 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 82,944 KB
実行使用メモリ 144,000 KB
最終ジャッジ日時 2025-06-12 15:49:52
合計ジャッジ時間 4,797 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
        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

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

    def add_line(self, new_line, node=None):
        if node is None:
            node = self.root

        l = node.l
        r = node.r
        m = node.m

        if node.line is None:
            node.line = new_line
            return

        current_val_left = node.line.get(l)
        new_val_left = new_line.get(l)
        current_val_right = node.line.get(r)
        new_val_right = new_line.get(r)

        if new_val_left > current_val_left and new_val_right > current_val_right:
            node.line = new_line
            return
        elif new_val_left <= current_val_left and new_val_right <= current_val_right:
            return
        else:
            if new_val_left > current_val_left:
                node.line, new_line = new_line, node.line

            if new_line.get(m) > node.line.get(m):
                temp = node.line
                node.line = new_line
                new_line = temp

            if new_line.get(l) > node.line.get(l):
                if not node.left:
                    node.left = LiChaoNode(l, m)
                self.add_line(new_line, node.left)
            else:
                if not node.right:
                    node.right = LiChaoNode(m + 1, r)
                self.add_line(new_line, node.right)

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

    def query(self, x, node=None):
        if node is None:
            node = self.root

        if node is None:
            return -float('inf')

        res = node.line.get(x) if node.line else -float('inf')

        m = node.m
        if x <= m:
            if node.left:
                res_left = self.query(x, node.left)
                res = max(res, res_left)
        else:
            if node.right:
                res_right = self.query(x, node.right)
                res = max(res, res_right)

        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
    
    dp = [0] * (N + 1)
    
    x_min = -10**5
    x_max = 10**5
    lct = LiChaoTree(x_min, x_max)
    
    for i in range(2, N + 1):
        if i == 2:
            option1 = dp[1] + Q[0] * Q[1]
            option2 = -float('inf')
        else:
            option1 = dp[i-1] + Q[i-2] * Q[i-1]
            option2 = lct.query(Q[i-1])
        
        dp[i] = max(option1, option2)
        
        if i >= 2:
            j = i - 1
            a = Q[j - 1]
            b = dp[j]
            lct.add(a, b)
    
    max_e = max(dp[2:N+1])
    print(max_e)

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