{"problem":{"name":"Slimes","description":{"content":"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 ope","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"dp_n"},"statements":[{"statement_type":"Markdown","content":"There are $N$ slimes lining up in a row. Initially, the $i$\\-th slime from the left has a size of $a_i$.\nTaro is trying to combine all the slimes into a larger slime. He will perform the following operation repeatedly until there is only one slime:\n\n*   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.\n\nFind the minimum possible total cost incurred.\n\n## Constraints\n\n*   All values in input are integers.\n*   $2 \\leq N \\leq 400$\n*   $1 \\leq a_i \\leq 10^9$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $a_2$ $\\ldots$ $a_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"dp_n","tags":[],"sample_group":[["4\n10 20 30 40","190\n\nTaro should do as follows (slimes being combined are shown in bold):\n\n*   (**10**, **20**, 30, 40) → (**30**, 30, 40)\n*   (**30**, **30**, 40) → (**60**, 40)\n*   (**60**, **40**) → (**100**)"],["5\n10 10 10 10 10","120\n\nTaro should do, for example, as follows:\n\n*   (**10**, **10**, 10, 10, 10) → (**20**, 10, 10, 10)\n*   (20, **10**, **10**, 10) → (20, **20**, 10)\n*   (20, **20**, **10**) → (20, **30**)\n*   (**20**, **30**) → (**50**)"],["3\n1000000000 1000000000 1000000000","5000000000\n\nThe answer may not fit into a 32-bit integer type."],["6\n7 6 8 6 1 1","68\n\nTaro should do, for example, as follows:\n\n*   (7, 6, 8, 6, **1**, **1**) → (7, 6, 8, 6, **2**)\n*   (7, 6, 8, **6**, **2**) → (7, 6, 8, **8**)\n*   (**7**, **6**, 8, 8) → (**13**, 8, 8)\n*   (13, **8**, **8**) → (13, **16**)\n*   (**13**, **16**) → (**29**)"]],"created_at":"2026-03-03 11:01:14"}}