結果

問題 No.913 木の燃やし方
ユーザー gew1fw
提出日時 2025-06-12 16:27:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,506 bytes
コンパイル時間 219 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 119,424 KB
最終ジャッジ日時 2025-06-12 16:27:43
合計ジャッジ時間 12,112 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 16 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff #

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

result = []

for i in range(1, n + 1):
    # 向右扩展
    r = i
    x = 1
    sum_val = A[i - 1]
    best_right = sum_val + x * x
    while r + 1 <= n:
        delta = 2 * x + 1 + A[r]
        if delta < 0:
            r += 1
            x += 1
            sum_val += A[r - 1]
            current = sum_val + x * x
            if current < best_right:
                best_right = current
        else:
            break

    # 向左扩展
    l = i
    x = 1
    sum_val = A[i - 1]
    best_left = sum_val + x * x
    while l - 1 >= 1:
        delta = 2 * x + 1 + A[l - 2]
        if delta < 0:
            l -= 1
            x += 1
            sum_val += A[l - 1]
            current = sum_val + x * x
            if current < best_left:
                best_left = current
        else:
            break

    # 计算区间[l, r]的总和
    sum_total = prefix[r] - prefix[l - 1]
    x_total = r - l + 1
    total_val = sum_total + x_total * x_total

    # 找出最小值
    min_val = min(best_right, best_left, total_val)

    # 比较整个数组的情况
    full_sum = prefix[n] - prefix[0]
    full_x = n
    full_val = full_sum + full_x * full_x
    min_val = min(min_val, full_val)

    # 比较单个i的情况
    single_val = 1 + A[i - 1]
    min_val = min(min_val, single_val)

    result.append(min_val)

for val in result:
    print(val)
0