結果

問題 No.913 木の燃やし方
ユーザー gew1fw
提出日時 2025-06-12 21:32:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,656 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 81,716 KB
実行使用メモリ 53,136 KB
最終ジャッジ日時 2025-06-12 21:33:42
合計ジャッジ時間 5,913 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff #

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    A = list(map(int, data[1:N+1]))
    
    if N == 0:
        return
    
    S = [0] * (N + 1)
    for i in range(1, N + 1):
        S[i] = S[i - 1] + A[i - 1]
    
    left_min = [0] * (N + 1)
    right_min = [0] * (N + 1)
    
    for i in range(1, N + 1):
        if i == 1:
            left_min[i] = (1)**2 + A[i-1]
        else:
            min_val = float('inf')
            for l in range(i, 0, -1):
                k = i - l + 1
                current = k**2 + (S[i] - S[l-1])
                if current < min_val:
                    min_val = current
                else:
                    break
            left_min[i] = min_val
    
    for i in range(N, 0, -1):
        if i == N:
            right_min[i] = (1)**2 + A[i-1]
        else:
            min_val = float('inf')
            for r in range(i, N + 1):
                k = r - i + 1
                current = k**2 + (S[r] - S[i-1])
                if current < min_val:
                    min_val = current
                else:
                    break
            right_min[i] = min_val
    
    result = []
    for i in range(1, N + 1):
        min_val = min(left_min[i], right_min[i])
        l = i
        while l >= 1:
            r = i
            while r <= N:
                k = r - l + 1
                current = k**2 + (S[r] - S[l-1])
                if current < min_val:
                    min_val = current
                r += 1
            l -= 1
        result.append(str(min_val))
    
    print('\n'.join(result))

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