P4983 Forgetfulness

"Why are you leaving me!" "Because you can't handle it!" "I can handle it!" "Fine, then maintain such a formula for me right now!" "Why would you give such a nasty thing." "To annoy you." "......" $…………………………….$

Your $npy$, in order to annoy you, specially invited four gurus and one noob! $\rm hdxrie$ said: "We need a sum." So we have $\sum\limits_{i=1}^{n} x_i$. $\rm Imagine$ said: "We need an average." So we have $\bar x$. $\rm TimeTraveller$ said: "We need addition, subtraction, multiplication, and division." So we have some nasty combinations. $\rm Althen·Way·Satan$ said: "We also need squaring." So we square it. The worst $\rm ZredXNy$ said: "Then I'll help you merge them." So we get the following expression: $$\frac{\left((\sum\limits_{i=1}^{n}x_i×\bar x)+\bar x\right)^2}{\bar x^2}$$ We define the value of a sequence as this expression, where $n$ is the number of elements in the sequence. Given a sequence of length $n$, you now need to split it into $m$ segments. The sum of the values of all segments should be as small as possible. Output this minimum value.

The first line contains two positive integers $n$ and $m$, as defined in the statement. The next line contains $n$ positive integers, giving the value of each element $x_i$ in order.

Output one integer, the minimum value.

- For $30\%$ of the data, $m \le n \le 500$. - For another $20\%$ of the data, it is guaranteed that $m = 2$. - For $100\%$ of the data, $m \le n \le 100000$, $1 \le x_i \le 1000$. Translated by ChatGPT 5