結果

問題 No.952 危険な火薬庫
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:18:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,726 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 81,712 KB
実行使用メモリ 267,296 KB
最終ジャッジ日時 2025-06-12 21:19:22
合計ジャッジ時間 14,682 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 22 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    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+2) for _ in range(N+2) ]
    
    for i in range(1, N+1):
        dp[i][1] = A[i-1] ** 2
    
    for j in range(2, N+1):
        cht_prev = deque()
        for i in range(1, N+1):
            if i < j:
                continue
            x = s[i]
            while len(cht_prev) >= 2:
                l1 = cht_prev[0]
                l2 = cht_prev[1]
                x_intersect = (l2[1] - l1[1]) / (l1[0] - l2[0])
                if x <= x_intersect:
                    cht_prev.popleft()
                else:
                    break
            if cht_prev:
                best_m, best_b = cht_prev[0]
                min_val = best_m * x + best_b
            else:
                min_val = INF
            
            dp[i][j] = x * x + min_val
            
            m_new = -2 * x
            b_new = dp[i][j] + x * x
            new_line = (m_new, b_new)
            while len(cht_prev) >= 2:
                l1 = cht_prev[-2]
                l2 = cht_prev[-1]
                x_intersect = (l2[1] - new_line[1]) / (new_line[0] - l2[0])
                if x_intersect <= x:
                    cht_prev.pop()
                else:
                    break
            cht_prev.append(new_line)
    
    for k in range(1, N+1):
        min_danger = INF
        for i in range(k, N+1):
            if dp[i][k] < min_danger:
                min_danger = dp[i][k]
        print(min_danger)
    print()

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