C - スペースエクスプローラー高橋君 解説

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 600600

問題文

あなたは大人気ゲーム 「スペースエクスプローラー高橋君」 で遊んでいます。 このゲームの目的は宇宙船すぬけ号の艦長である高橋君となって、宇宙一の探検家を目指すことです。 現在あなたは 宇宙で一番おいしいりんご が宙域 RNG-58 にあることを突き止め、 RNG-58 へ向かっています。
宇宙で一番おいしいりんごは宇宙一おいしいので、宇宙海賊の青木君がすぬけ号を狙ってやってきました。 青木君は宇宙船けぬす号(すぬけ号の同型艦です)の艦長であり、高橋君のライバルです。 すぬけ号に取り付けられたすぬけキャノンでけぬす号を撃破しましょう!

けぬす号は 11 番から NN 番までの番号がついた NN ヶ所の区画からなり、区画 ii の防御力は aia_i です。 すぬけ号に取り付けられたすぬけキャノンは NN 門あり、11 番から NN 番までの番号がついています。 ii 番のすぬけキャノンでけぬす号の区画 jj を破壊するには aj+(ji)2a_j + (j-i)^{2} だけエネルギーを消費します。

どこか 11 つの区画を破壊すればけぬす号を撃破可能ですが、あなたは今後の航行のためにもなるべくすぬけ号のエネルギーを温存したいです。 それぞれのすぬけキャノンについて、けぬす号を撃破するのに最小限必要なエネルギーを求めてください。

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1ai10121 \leq a_i \leq 10^{12}
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

NN
a1a_1 a2a_2 ...... aNa_{N}

出力

答えを NN 行に出力せよ。ii 行目では ii 番のすぬけキャノンにより、けぬす号を撃破するのに最小限必要なエネルギーを出力せよ。


入力例 1Copy

Copy
3
1 3 2

出力例 1Copy

Copy
1
2
2

入力例 2Copy

Copy
11
1 3 6 10 15 18 15 10 6 3 1

出力例 2Copy

Copy
1
2
4
7
10
14
10
7
4
2
1

入力例 3Copy

Copy
12
10 14 64 20 24 12 12 21 30 44 29 2

出力例 3Copy

Copy
10
11
14
16
13
12
12
13
11
6
3
2


2025-04-03 (木)
09:24:50 +00:00