問題一覧 > 通常問題

No.952 危険な火薬庫

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 32
作問者 : Shuz*Shuz* / テスター : 👑 tatyamtatyam
3 ProblemId : 3323 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-12-01 09:35:17

問題文

$N$ 個のドアが設置された火薬庫があり、ドアには左から順に $1,\ 2,\ \dots,\ N$ の番号がつけられています。
各ドア $i$ には、そのドアが開いているときの危険度 $A_i$ が定まっており、現在すべてのドアが閉まっています。
これから換気のために、ドアをいくつか開けることを考えています。
ドアをいくつか開けたときの火薬庫の危険度は以下のように定義されます。

  • ドア $L,\ L+1,\ \dots,\ R$ が開いていて、かつドア $L-1,\ R+1$ が閉まっている / 存在しないようなドアの集合 ( ドア $L,\ L+1,\ \dots,\ R$ ) を $1$ つの連結成分とし、この連結成分の危険度を ${\left(\displaystyle \sum_{L\le i\le R} A_i \right)}^2$ とする。
  • 火薬庫の危険度をすべての連結成分の危険度の和とする。

    • 各 $k = 1,\ 2,\ ...,\ N$ に対して、適切に開けるドアを $k$ 個選んだときの火薬庫の危険度の最小値を求めてください。

    制約

  • 入力はすべて整数
  • $1\le N\le 3000$
  • $1\le A_i\le 100000$

    • 入力

    $N$
$A_1\ A_2\ \dots \ A_N$

    $N$ はドアの個数。
    $A_i$ はドア $i$ が開いているときの危険度。

    出力

    $k\ (1\le k\le N)$ 行目には、開けるドアを $k$ 個適切に選んだときの、火薬庫の危険度の最小値を出力してください。
    最後に改行してください。

    サンプル

    サンプル1
    入力
    5
1 2 3 4 5
    出力
    1
9
25
61
225

    開けるドアの個数 $\qquad$ 開けるドアの組 $\qquad$ 火薬庫の危険度の最小値 $\qquad$
    $1$ $1$ $1^2=1$
    $2$ $1,\ 2$ $(1+2)^2=9$
    $3$ $1,\ 2,\ 4$ $(1+2)^2+4^2=25$
    $4$ $1,\ 2,\ 3,\ 5$ $(1+2+3)^2+5^2=61$
    $5$ $1,\ 2,\ 3,\ 4,\ 5$ $(1+2+3+4+5)^2=225$
    サンプル2
    入力
    7
10000 10001 10002 10003 10001 10000 10002
    出力
    100000000
200000000
300040004
400100009
900180014
1800360018
4901260081

    サンプル4
    入力
    10
1 2 3 4 5 6 7 8 9 10
    出力
    1
9
25
61
110
191
300
550
1145
3025

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