P17457 [GESP202609 Level 6] Array Partition

You are given an array $A=[a_1,a_2,\ldots,a_n]$ consisting of $n$ integers. You need to partition array $A$ into several non-empty contiguous subsegments. For any subsegment obtained by the partition, its deviation value is defined as the square of the sum of the integers in that subsegment. The deviation value of a partition plan is defined as the sum of the deviation values of all subsegments. You need to minimize the deviation value of the partition plan. Formally, you can partition $A$ into several non-empty contiguous subsegments $A_1,A_2,\ldots,A_k$ such that $A=A_1+A_2+\ldots+A_k$, where $+$ denotes concatenation of arrays. For $1\le i\le k$, let $A_i=[a_1^{(i)},\ldots,a_{m_i}^{(i)}]$ contain $m_i$ integers. You need to minimize $\sum_{i=1}^{k}\left(\sum_{j=1}^{m_i}a_j^{(i)}\right)^2$.

The first line contains a positive integer $n$, representing the length of array $A$. The second line contains $n$ integers $a_1,a_2,\ldots,a_n$, representing array $A$.

One line containing one integer, representing the minimum possible deviation value of the partition plan.

For $40\%$ of the test points, it is guaranteed that $0\le a_i\le 50$. For all test points, it is guaranteed that $1\le n\le 2000$ and $-100\le a_i\le 100$. Translated by ChatGPT 5