結果

問題 No.952 危険な火薬庫
ユーザー gew1fw
提出日時 2025-06-12 13:57:33
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,821 bytes
コンパイル時間 594 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 159,676 KB
最終ジャッジ日時 2025-06-12 13:58:00
合計ジャッジ時間 4,153 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    S = [0] * (N + 1)
    for i in range(N):
        S[i+1] = S[i] + A[i]
    
    INF = float('inf')
    dp = [ [INF] * (N + 1) for _ in range(N + 1) ]
    dp[0][0] = 0
    
    for j in range(1, N + 1):
        for i in range(N + 1):
            if i == 0:
                dp[j][i] = INF
            else:
                dp[j][i] = dp[j][i-1]
        
        cht = []
        for i in range(1, N + 1):
            s_lower = max(1, i - j + 2)
            s_upper = i
            new_lines = []
            for s in range(s_lower, s_upper + 1):
                j_prime = j - i + s - 1
                if j_prime < 0:
                    continue
                if s - 2 < 0:
                    continue
                if j_prime > j - 1:
                    continue
                if dp[j_prime][s-2] == INF:
                    continue
                a = -2 * S[s-1]
                b = dp[j_prime][s-2] + S[s-1] ** 2
                new_lines.append((a, b))
            
            if j == i:
                sum_val = S[i] - S[0]
                current = sum_val ** 2
                if current < dp[j][i]:
                    dp[j][i] = current
            
            for a, b in new_lines:
                while len(cht) >= 2:
                    a1, b1 = cht[-2]
                    a2, b2 = cht[-1]
                    x1 = (b - b2) / (a2 - a) if a != a2 else (b2 - b) * float('inf')
                    x2 = (b1 - b2) / (a2 - a1) if a1 != a2 else (b2 - b1) * float('inf')
                    if x1 <= x2:
                        cht.pop()
                    else:
                        break
                if not cht or (cht[-1][0] != a) or (cht[-1][0] == a and b < cht[-1][1]):
                    cht.append((a, b))
            
            if not cht:
                current = INF
            else:
                x = S[i]
                left = 0
                right = len(cht) - 1
                while left < right:
                    mid = (left + right) // 2
                    a1, b1 = cht[mid]
                    a2, b2 = cht[mid + 1]
                    val1 = a1 * x + b1
                    val2 = a2 * x + b2
                    if val1 > val2:
                        left = mid + 1
                    else:
                        right = mid
                a, b = cht[left]
                current = a * x + b
            
            temp = S[i] ** 2 + current
            if temp < dp[j][i]:
                dp[j][i] = temp
            if i > 0 and dp[j][i] > dp[j][i-1]:
                dp[j][i] = dp[j][i-1]
    
    for k in range(1, N + 1):
        print(dp[k][N])

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