Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

These problems are from the atcoder DP contest, and were transferred onto DMOJ. All problem statements were made by several atcoder users. As there is no access to the test data, all data is randomly generated. If there are issues with the statement or data, please contact Rimuru or Ninjaclasher on slack.

There are N slimes lining up in a row. Initially, the i-th slime from the left has a size of a_i.

Taro is trying to combine all the slimes into a larger slime. He will perform the following operation repeatedly until there is only one slime:

  • Choose two adjacent slimes, and combine them into a new slime. The new slime has a size of x+y, where x and y are the sizes of the slimes before combining them. Here, a cost of x+y is incurred. The positional relationship of the slimes does not change while combining slimes.

Find the minimum possible total cost incurred.

Constraints

  • All values in input are integers.
  • 2 \le N \le 400
  • 1 \le a_i \le 10^9

Input Specification

The first line will contain the integer N.

The next line will contain N integers, a_1, a_2, \ldots, a_N.

Output Specification

Print the minimum possible total cost incurred.

Note: The answer may not fit into a 32-bit integer type.

Sample Input 1

4
10 20 30 40

Sample Output 1

190

Explanation For Sample 1

Taro should do as follows (slimes being combined are shown in bold):

  • (10, 20, 30, 40) \rightarrow (30, 30, 40)
  • (30, 30, 40) \rightarrow (60, 40)
  • (60, 40) \rightarrow (100)

Sample Input 2

5
10 10 10 10 10

Sample Output 2

120

Explanation For Sample 2

Taro should do, for example, as follows:

  • (10, 10, 10, 10, 10) \rightarrow (20, 10, 10, 10)
  • (20, 10, 10, 10) \rightarrow (20, 20, 10)
  • (20, 20, 10) \rightarrow (20, 30)
  • (20, 30) \rightarrow (50)

Sample Input 3

3
1000000000 1000000000 1000000000

Sample Output 3

5000000000

Sample Input 4

6
7 6 8 6 1 1

Sample Output 4

68

Explanation For Sample 4

Taro should do, for example, as follows:

  • (7, 6, 8, 6, 1, 1) \rightarrow (7, 6, 8, 6, 2)
  • (7, 6, 8, 6, 2) \rightarrow (7, 6, 8, 8)
  • (7, 6, 8, 8) \rightarrow (13, 8, 8)
  • (13, 8, 8) \rightarrow (13, 16)
  • (13, 16) \rightarrow (29)

Comments

There are no comments at the moment.