18760번 - Heavy Stones 다국어

After learning Garsia–Wachs algorithm, you came up with the following problem.

There are n piles of stones in a line. The i-th pile contains ai stones. You want to merge all the stones into one pile.

At first, you will select the k-th pile. Then you can do the following operation on the selected pile: Choose the left or right adjacent pile of the selected one, and merge them into one pile. The new pile becomes the selected pile after the operation. After doing this operation n − 1 times, there will be only one pile left. The cost of each merge operation is the number of stones in the new pile.

You want to know the smallest total cost if you select the k-th pile initially. For k = 1, 2, . . . , n, output the answer.

The first line contains an integer n (1 ≤ n ≤ 2 · 10⁵).

The second line contains n integers a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10⁶).

Output n integers. The k-th number indicates the smallest total cost if you select the k-th pile initially.

If you select the 4-th pile initially, the process can go as follows:

{2, 1, 3, 5, 4} → {2, 1, 8, 4} → {2, 9, 4} → {11, 4} → {15}.

The total cost is 8 + 9 + 11 + 15 = 43.