問題一覧 > 通常問題

No.913 木の燃やし方

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 : ei1333333ei1333333 / テスター : treeonetreeone
4 ProblemId : 3421 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-10-18 13:25:32

問題文

$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

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