結果

問題 No.952 危険な火薬庫
コンテスト
ユーザー lam6er
提出日時 2025-04-09 20:56:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,220 bytes
コンパイル時間 509 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 136,860 KB
最終ジャッジ日時 2025-04-09 20:57:14
合計ジャッジ時間 4,164 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
A = list(map(int, input().split()))
prefix = [0] * (n + 1)
for i in range(n):
    prefix[i+1] = prefix[i] + A[i]

INF = float('inf')
dp = [ [INF] * (n + 1) for _ in range(n + 1) ]
dp[0][0] = 0

for i in range(1, n + 1):
    for j in range(0, n + 1):
        # Option 1: Do not open the i-th door
        dp[i][j] = min(dp[i][j], dp[i-1][j])
        # Option 2: Open the i-th door, part of a block ending here
        # Try all possible starts s for the block ending at i
        for s in range(1, i + 1):
            doors_opened = i - s + 1
            if j < doors_opened:
                continue
            # sum is prefix[i] - prefix[s-1]
            sum_block = prefix[i] - prefix[s-1]
            prev_j = j - doors_opened
            prev_i = s - 2  # the block must be separated by at least one closed door
            if prev_i >= 0:
                if dp[prev_i][prev_j] == INF:
                    continue
                new_val = dp[prev_i][prev_j] + sum_block * sum_block
                dp[i][j] = min(dp[i][j], new_val)
            else:
                if prev_j == 0:
                    dp[i][j] = min(dp[i][j], sum_block * sum_block)

for k in range(1, n + 1):
    print(dp[n][k])
0