3711. 社区规划

【题目描述】

街道上共有$m$个相邻的小区，每个小区的人数为$x_i$。现要将这$m$个小区划分为$n$个社区，为了方便管理，要求每个社区必须为连续的几个小区，不能穿插，且要求各个社区的人数尽量相等，即方差最小。为方便起见，你只需输出最小方差的$n^2$倍。

【输入格式】

第一行两个正整数，$m,n$

第二行$m$个正整数，第$i$个表示$x_i$

【输出格式】

一个正整数，表示最小方差的$n^2$倍

【样例输入】

4 2
1 2 3 4

【样例输出】

4

【样例说明】

将小区划分为(1,2,3)(4)两个社区，平均数为$\frac{6+4}{2}=5$，方差为$\frac{1}{2}[(6-5)^2+(4-5)^2]=1$

【数据规模与约定】

$1≤n≤m≤5000，x_i≤1000$

【来源】

$rsr$