結果

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

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    idx += N
    
    prefix = [0] * (N + 1)
    for i in range(1, N+1):
        prefix[i] = prefix[i-1] + A[i-1]
    
    INF = float('inf')
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    
    for j in range(1, N+1):
        dp[j][0] = INF
    
    opt = [[0]*(N+2) for _ in range(N+2)]
    
    for i in range(1, N+1):
        dp[1][i] = (prefix[i] - prefix[i-1]) ** 2
    
    for j in range(2, N+1):
        opt[j][N+1] = N
        for i in reversed(range(1, N+1)):
            mn = INF
            l = opt[j][i+1] if i < N else 1
            r = opt[j-1][i] if j > 1 else i
            r = min(r, i)
            for s in range(l, r+1):
                if s-2 < 0:
                    prev = 0 if j - (i - s + 1) == 0 else INF
                else:
                    prev = dp[j - (i - s + 1)][s-2]
                if prev == INF:
                    continue
                current = prev + (prefix[i] - prefix[s-1]) ** 2
                if current < mn:
                    mn = current
                    opt[j][i] = s
            dp[j][i] = mn if mn != INF else INF
    
    for j in range(1, N+1):
        res = INF
        for i in range(j, N+1):
            res = min(res, dp[j][i])
        print(res)
    
if __name__ == '__main__':
    main()
0