結果
問題 |
No.913 木の燃やし方
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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)