問題一覧 > 通常問題

No.952 Dangerous Powder Magazine

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 39
作問者 : Shuz* / テスター : tatyam
お気に入りにしたユーザー ProblemId : 3323 / 自分の提出
問題文最終更新日: 2019-12-01 09:35:17
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
Advent Calendar Contest 2019 (順位表) の他の問題:

Problem Statement

There is a powder magazine with $N$ doors, numbered $1,\ 2,\ \dots,\ N$ from left to right.
Each door $i$ has a fixed danger level $A_i$ that applies when the door is open. Currently, all doors are closed.
You are going to open some of the doors for ventilation.
The danger level of the powder magazine when some doors are open is defined as follows.

  • A set of doors (doors $L,\ L+1,\ \dots,\ R$) such that doors $L,\ L+1,\ \dots,\ R$ are open and each of doors $L-1,\ R+1$ is closed or does not exist forms $1$ connected component, and the danger level of this connected component is ${\left(\displaystyle \sum_{L\le i\le R} A_i \right)}^2$.
  • The danger level of the powder magazine is the sum of the danger levels of all connected components.

    • For each $k = 1,\ 2,\ ...,\ N$, find the minimum danger level of the powder magazine when $k$ doors to open are chosen appropriately.

    Constraints

  • All input values are integers.
  • $1\le N\le 3000$
  • $1\le A_i\le 100000$

    • Input

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

    $N$ is the number of doors.
    $A_i$ is the danger level of door $i$ when it is open.

    Output

    On line $k\ (1\le k\le N)$, print the minimum danger level of the powder magazine when $k$ doors to open are chosen appropriately.
    Print a newline at the end.

    Sample

    Sample 1
    Input
    5
1 2 3 4 5
    Output
    1
9
25
61
225

    Number of doors to open $\qquad$ Doors to open $\qquad$ Minimum danger level of the powder magazine $\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$
    Sample 2
    Input
    7
10000 10001 10002 10003 10001 10000 10002
    Output
    100000000
200000000
300040004
400100009
900180014
1800360018
4901260081

    Sample 4
    Input
    10
1 2 3 4 5 6 7 8 9 10
    Output
    1
9
25
61
110
191
300
550
1145
3025

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