30pts 已经对着题解看了好几遍了，还是不知道哪里错了...

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 3e4 + 10;

long long s[MAXN];
long long n,m;
int que[MAXN],head = 0,tail = 0;
long long f[MAXN],t[MAXN],g[MAXN];

double calc(int x,int y) {
	long long A1 = g[x] + s[x] * s[x],A2 = g[y] + s[y] * s[y];
	return double((A1 - A2)) / (s[x] - s[y]) * 1.0;
}

int main() {
	scanf("%lld%lld",&n,&m);
	for (int i = 1; i <= n; i++) {
		scanf("%lld",&s[i]);
		s[i] += s[i - 1];
		g[i] = s[i] * s[i];
	}
	for (int i = 2; i <= m; i++) {
		tail = 0,head = 1;
		for (int j = 1; j <= n; j++) {
			while (head < tail && calc(que[head],que[head + 1]) <= 2.0 * s[j]) head++;
			f[j] = g[que[head]] + (s[j] - s[que[head]]) * (s[j] - s[que[head]]);
			while (head < tail && calc(que[tail],que[tail - 1] >= calc(j,que[tail - 1]))) tail--;
			que[++tail] = j;
		}
		for (int j = 1; j <= n; j++) g[j] = f[j];
	}
	cout << m * f[n] - s[n] * s[n] << endl;
	return 0;
}