P4072 [SDOI2016] The Journey

Pine starts a journey from $S$ to $T$. The road from $S$ to $T$ can be divided into $n$ segments, and there is a rest station at the boundary point between each pair of adjacent segments. Pine plans to reach $T$ in $m$ days. Except for day $m$, Pine must spend each night at a rest station. Therefore, each segment must be completed within a single day. Pine wants the daily distances to be as similar as possible, so he wants the variance of the daily distances to be as small as possible. Help Pine find the minimum possible variance. Let the variance be $v$. It can be proven that $v \times m^2$ is an integer. To avoid precision errors, output $v \times m^2$.

The first line contains two integers $n, m$. The second line contains $n$ integers, representing the lengths of the $n$ segments.

Output a single integer: the minimum variance multiplied by $m^2$.

- Constraints and Conventions - For $30\%$ of the testdata, $1 \le n \le 10$; - For $60\%$ of the testdata, $1 \le n \le 100$; - For $100\%$ of the testdata, $1 \le n \le 3000$. The total distance from $S$ to $T$ does not exceed $3 \times 10^4$. $2 \le m \le n$, and each segment length is a positive integer not exceeding $3 \times 10^4$. Translated by ChatGPT 5