問題一覧 > 通常問題

No.913 How to Burn Trees

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 35
作問者 : ei1333333 / テスター : treeone
お気に入りにしたユーザー ProblemId : 3421 / 自分の提出
問題文最終更新日: 2019-10-18 13:25:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 228 (順位表) の他の問題:

Problem Statement

$N$ trees are planted in a horizontal row, and the value of the $i$-th tree from the left is $A_i$.

You will now choose any contiguous segment and burn all the trees in the segment. Here, the sadness is defined as $x^2 +$ (the sum of the values of the burned trees), where $x$ is the number of burned trees.

For each tree, find the minimum sadness when that tree must be burned.

Input

$N$
$A_1$ $A_2$ $\cdots$ $A_N$
  • $1 \leq N \leq 2 \times 10^5$
  • $|A_i| \leq 10^9$
  • All inputs are integers.

Output

Output $N$ lines. On the $i$-th line, output the minimum sadness when the $i$-th tree from the left must be burned.

Sample

Sample 1
Input
3
-2 -5 100
Output
-3
-4
99
  • If tree $1$ must be burned, it is optimal to burn trees $[1, 2]$, and the sadness in this case is $2^2+(-2-5)=-3$.
  • If tree $2$ must be burned, it is optimal to burn trees $[2, 2]$, and the sadness in this case is $1^2+(-5)=-4$.
  • If tree $3$ must be burned, it is optimal to burn trees $[2, 3]$, and the sadness in this case is $2^2+(-5+100)=99$.
Sample 2
Input
5
-10000 0 -10000 0 -10000
Output
-29975
-29975
-29975
-29975
-29975

No matter which tree must be burned, it is optimal to burn all the trees.

Sample 3
Input
1
0
Output
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。