P4805 [CCC 2016] Combining Riceballs

**Translated from [CCC2016](https://cemc.math.uwaterloo.ca/contests/computing/2016/index.html) Senior T4 “[Combining Riceballs](https://cemc.math.uwaterloo.ca/contests/computing/2016/stage%201/seniorEn.pdf)”** Alphonse has $N$ delicious riceballs of different sizes, arranged in a line. He wants to give the largest riceball to his best friend. He can perform the following operations: - If two **adjacent** riceballs have the same size, Alphonse can combine them into one new riceball. The new riceball’s size is the sum of the two original riceballs’ sizes. It will occupy the positions previously occupied by the two original riceballs. - If two riceballs have the same size, and there is exactly one riceball between them, Alphonse can also combine them into one new riceball. (There is no restriction on the middle riceball’s size.) The new riceball’s size is the sum of the three original riceballs’ sizes, and it occupies the positions previously occupied by the three original riceballs. Alphonse may perform the operations any number of times, in any order. After performing $0$ or more operations, determine which riceball he should give to his friend.

The first line contains an integer $N$ $(1 \le N \le 400)$. The second line contains $N$ space-separated integers, giving the sizes of the riceballs from left to right. Each integer is at most $1\ 000\ 000$.

Output the maximum riceball size that Alphonse can obtain.

#### Sample Explanation 1. One possible sequence of merges is: combine the two riceballs of size $12$ to get a riceball of size $24$. Then combine the two riceballs of size $9$ to get a riceball of size $18$. Next, combine the three riceballs of size $3, 18,$ and $3$ to get a riceball of size $24$. Finally, combine the two riceballs of size $24$ to get a riceball of size $48$. #### Sample Explanation 2. We cannot perform any operation, so the answer is $3$. For $\frac1{15}$ of the testdata, $N = 4$. For another $\frac2{15}$ of the testdata, $N \le 10$. For another $\frac5{15}$ of the testdata, $N \le 50$. Translated by ChatGPT 5