結果

問題 No.952 危険な火薬庫
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:29:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,268 bytes
コンパイル時間 367 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 151,040 KB
最終ジャッジ日時 2025-06-12 16:29:20
合計ジャッジ時間 4,081 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    S = [0] * (N + 1)
    for i in range(1, N+1):
        S[i] = S[i-1] + A[i-1]
    
    INF = float('inf')
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    
    deques = [deque() for _ in range(N + 2)]
    
    for j in range(1, N+1):
        deques[j].clear()
        for i in range(1, N+1):
            if j > i:
                continue
            x = S[i]
            # Query the deque for j
            dq = deques[j]
            while len(dq) >= 2:
                l1 = dq[0]
                l2 = dq[1]
                m1, a1 = l1
                m2, a2 = l2
                if m1 == m2:
                    x_intersect = INF
                else:
                    x_intersect = (a2 - a1) / (m1 - m2)
                if x_intersect < x:
                    dq.popleft()
                else:
                    break
            if dq:
                best_line = dq[0]
                current = best_line[0] * x + best_line[1]
                dp[i][j] = x * x + current
            else:
                continue
            # Add the new line to deque[j+1] if j < N
            if j < N:
                m = -2 * x
                a_val = dp[i][j] + x * x
                # Append to deques[j+1]
                new_line = (m, a_val)
                dq_j_plus_1 = deques[j+1]
                while len(dq_j_plus_1) >= 2:
                    l1 = dq_j_plus_1[-2]
                    l2 = dq_j_plus_1[-1]
                    m1, a1 = l1
                    m2, a2 = l2
                    m_new, a_new = new_line
                    if m2 == m1:
                        x1 = INF
                    else:
                        x1 = (a2 - a1) / (m1 - m2)
                    if m_new == m2:
                        x2 = INF
                    else:
                        x2 = (a_new - a2) / (m2 - m_new)
                    if x1 >= x2:
                        dq_j_plus_1.pop()
                    else:
                        break
                dq_j_plus_1.append(new_line)
    
    for k in range(1, N+1):
        print(dp[N][k])

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