我的：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int in(){int k=0,f=1;char c=getchar();while (c<'0'||c>'9'){if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9'){k=k*10+c-'0';c=getchar();}return k*f;}
int n,m,f[3005][3005],q[3005],s[3005];
const int inf=1e9;
double fc(int x,int y,int z){return 1.0*(f[x][y]-f[x][z]+s[y]*s[y]-s[z]*s[z])/(s[y]-s[z]);}
signed main()
{
	n=in();m=in();
	for (int i=0;i<=3001;i++) for (int j=0;j<=3001;j++) f[i][j]=inf;f[0][0]=0;
	for (int i=1;i<=n;i++) s[i]=s[i-1]+in();
	for (int i=1;i<=n;i++) f[1][i]=s[i]*s[i];
	for (int i=2;i<=m;i++)
	{
		int h=1,t=0;
		for (int j=1;j<=n;j++)
		{
			while (h<t&&fc(i-1,q[h],q[h+1])<s[j]*2) h++;
			int k=q[h];
			f[i][j]=f[i-1][j]+(s[k]-s[j])*(s[k]-s[j]);
			while (h<t&&fc(i-1,q[t-1],q[t])>fc(i-1,q[t],j)) t--;
			q[++t]=j;
		}
	}
	printf("%lld",m*f[m][n]-s[n]*s[n]);
	return 0;
}

std：

#include<cstring>
#include<cstdio>
#include<queue>
#define N 3005
#define int long long

int f[N][N];
int que[N];
int sl[N];
int l[N];
int n,m;

double slope(int u,int j,int k){return 1.0*(f[u][j]-f[u][k]+sl[j]*sl[j]-sl[k]*sl[k])/(sl[j]-sl[k]);}

main(){
	scanf("%lld%lld",&n,&m);
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;++i)scanf("%lld",&l[i]);
	for(int i=1;i<=n;++i)sl[i]=sl[i-1]+l[i];
	int h,t;
	f[0][0]=0;
	for(int i=1;i<=n;i++)f[1][i]=sl[i]*sl[i];
    for(int p=2;p<=m;p++){
        h=1,t=0;
        for(int i=1;i<=n;i++) { 
            while(h<t&&slope(p-1,que[h],que[h+1])<2*sl[i])h++;
            int j=que[h];
            f[p][i]=f[p-1][j]+(sl[j]-sl[i])*(sl[j]-sl[i]); 
            while(h<t&&slope(p-1,que[t-1],que[t])>slope(p-1,que[t],i))t--;
            que[++t]=i;
        }
    }
    int ans=m*f[m][n]-sl[n]*sl[n];
    printf("%lld\n",ans);
	return 0;
}