No.913 木の燃やし方

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 19
作問者 : TaprisちゃんTaprisちゃん / テスター : treeonetreeone
1 ProblemId : 3421 / 出題時の順位表

問題文

$N$ 本の木が横一列に植えられていて, 左から $i$ 番目の木の価値は $A_i$ です。

これから好きな連続する区間を選んで, 区間内にある木を全て燃やします。 ここで, 悲しさを燃やした木の本数を $x$ として $x^2 +$ (燃やした木の価値の総和) と定義します。

それぞれの木について, その木を必ず燃やす場合の悲しさの最小値を求めてください。

入力

$N$
$A_1$ $A_2$ $\cdots$ $A_N$
  • $1 \leq N \leq 2 \times 10^5$
  • $|A_i| \leq 10^9$
  • 入力はすべて整数

出力

出力は $N$ 行からなります。$i$ 行目には左から $i$ 番目の木を必ず燃やす場合の悲しさの最小値を出力してください。

サンプル

サンプル1
入力
3
-2 -5 100
出力
-3
-4
99
  • 木 $1$ を必ず燃やす場合, 木 $[1, 2]$ を燃やすのが最適でこのときの悲しさは $2^2+(-2-5)=-3$ です。
  • 木 $2$ を必ず燃やす場合, 木 $[2, 2]$ を燃やすのが最適でこのときの悲しさは $1^2+(-5)=-4$ です。
  • 木 $3$ を必ず燃やす場合, 木 $[2, 3]$ を燃やすのが最適でこのときの悲しさは $2^2+(-5+100)=99$ です。
サンプル2
入力
5
-10000 0 -10000 0 -10000
出力
-29975
-29975
-29975
-29975
-29975

どの木を必ず燃やす場合でも, すべての木を燃やすのが最適です。

サンプル3
入力
1
0
出力
1
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。