好久没写斜率优化板子都忘了，
硬是交了十几遍。。
推一下柿子就能得到答案为
[m*sum x^2-(sum x)^2
]
后面是个定值，前面简单dp，斜率优化一下就行了。
(f[i][j]=f[k][j-1]+sum[i]*sum[i]-2sum[i]sum[k]+sum[k]*sum[k])
(-f[k][j-1]-sum[k]*sum[k]=-2sum[i]sum[k]-f[i][j]+sum[i]*sum[i])
#include <cstdio>
#include <cstring>
const int MAXN = 3010;
int n, m;
int f[MAXN][MAXN], sum[MAXN];
inline double k(int j, int i, int k){
return ((double)f[i][j - 1] + sum[i] * sum[i] - f[k][j - 1] - sum[k] * sum[k]) / ((double)sum[i] - sum[k]);
}
inline int min(int a, int b){
return a > b ? b : a;
}
int q[MAXN], head, tail;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i){
scanf("%d", &sum[i]); sum[i] += sum[i - 1];
}
memset(f, 31, sizeof f);
for(int i = 1; i <= n; ++i) f[i][1] = sum[i] * sum[i];
for(int j = 2; j <= m; ++j){
head = tail = 0;
for(int i = 1; i <= n; ++i){
while(head < tail && k(j, q[head], q[head + 1]) < 2 * sum[i]) ++head;
int K = q[head];
f[i][j] = f[K][j - 1] + (sum[i] - sum[K]) * (sum[i] - sum[K]);
while(head < tail && k(j, q[tail - 1], q[tail]) >= k(j, q[tail], i)) --tail;
q[++tail] = i;
}
}
/*for(int j = 1; j <= m; ++j)
for(int i = 1; i <= n; ++i)
for(int k = 0; k < i; ++k)
f[i][j] = min(f[i][j], f[k][j - 1] + (sum[i] - sum[k]) * (sum[i] - sum[k]));*/
printf("%d
", m * f[n][m] - sum[n] * sum[n]);
return 0;
}