問題一覧 > 通常問題

No.3613 Legendary Bread Maker

レベル : / AI推定難易度 : 750 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 41
作問者 : Unbakedbread / テスター : kazuppa Tamiji153
お気に入りにしたユーザー ProblemId : 13656 / 自分の提出
問題文最終更新日: 2026-08-06 14:45:11
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
Paken新入生コンday1 (順位表) の他の問題:

Problem Statement

Bread, a legendary bread maker, has $N$ baguettes. The length of the $i$-th baguette is $A_i$.

Bread is about to perform "Bread Arrangement", a traditional ritual for combining the baguettes into $1$.

First, to prepare for "Bread Arrangement", he lines up the baguettes in a row so that the $i$-th baguette is placed $i$-th from the left, forming $1$ row. Then, he repeats the following operation until 1 baguette remains.

  • Choose $2$ adjacent baguettes. Let the lengths of the $2$ baguettes be $X,Y$ respectively. Using these $2$ baguettes and $X \times Y$ gold, make $1$ baguette of length $X+Y$. Then, place the new baguette at the right end or the left end of the row. The baguettes used disappear.

Bread is stingy, so he wants to keep the amount of gold used in "Bread Arrangement" as small as possible.

Find the minimum amount of gold used, for Bread's sake.

Constraints

  • $2 \le N \le 2 \times 10^5$
  • $1 \le A_i \le 10^4$
  • All input values are integers.

Subtasks

This problem has partial scoring by subtasks.

Subtask name Score Constraints
Subtask 120 points$N=2$
Subtask 280 points$N\leq 8$
Subtask 3100 pointsNo additional constraints

Input

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

Output

Print the minimum amount of gold Bread uses in "Bread Arrangement".

Sample

Sample 1
Input
4
3 1 4 1
Output
27

This input satisfies the constraints of Subtasks $1,2$.

Sample 2
Input
2
10000 10000
Output
100000000

This input satisfies the constraints of all subtasks.

Sample 3
Input
12
1 1 1 1 1 1 1 1 1 1 1 1
Output
66

This input satisfies the constraints of Subtask $3$.

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