No.3613 Legendary Bread Maker
タグ : / 解いたユーザー数 41
作問者 :
kazuppa
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 1 | 20 points | $N=2$ |
| Subtask 2 | 80 points | $N\leq 8$ |
| Subtask 3 | 100 points | No 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もしくは右上の雲マークをクリックしてアカウントを作成してください。