```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=3100;
int a[N];LL s[N],f[N][N];
int l,r,Q[N];
double X(int j){return 1.0*s[j];}
double Y(int j,int k){return 1.0*(f[j][k-1]+s[j]*s[j]);}
double slop(int j1,int j2,int k){
if(!(X(j2)-X(j1)))return 1e18;
return (Y(j2,k)-Y(j1,k))/(X(j2)-X(j1));
}
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
s[i]=s[i-1]+a[i];
}
for(int i=0;i<=n;i++)f[i][1]=s[i]*s[i];
for(int k=2;k<=m;k++){
l=r=1;Q[l]=0;
for(int i=1;i<=n;i++){
while(l<r&&slop(Q[l],Q[l+1],k)<2.0*s[i])l++;
int j=Q[l];
f[i][k]=f[j][k-1]+(s[i]-s[j])*(s[i]-s[j]);
while(l<r&&slop(Q[r-1],Q[r],k)>slop(Q[r],i,k))r--;
Q[++r]=i;
}
}
printf("%lld",-s[n]*s[n]+f[n][m]*m);
return 0;
}
```
by reclusive @ 2023-09-12 09:04:49
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=3100;
int a[N];LL s[N],f[N][N];
int l,r,Q[N];
double X(int j){return 1.0*s[j];}
double Y(int j,int k){return 1.0*(f[j][k-1]+s[j]*s[j]);}
double slop(int j1,int j2,int k){
if(!(X(j2)-X(j1)))return 1e18;
return (Y(j2,k)-Y(j1,k))/(X(j2)-X(j1));
}
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;i++)f[i][1]=s[i]*s[i];
for(int k=2;k<=m;k++){
l=r=1;Q[l]=0;
for(int i=1;i<=n;i++){
while(1){
if(l>=r)break;
if(X(Q[l+1])-X(Q[l])<0){
if((Y(Q[l+1],k)-Y(Q[l],k))>2.0*s[i]*(X(Q[l+1])-X(Q[l])))l++;
else break;
}
else{
if((Y(Q[l+1],k)-Y(Q[l],k))<2.0*s[i]*(X(Q[l+1])-X(Q[l])))l++;
else break;
}
}
int j=Q[l];
f[i][k]=f[j][k-1]+(s[i]-s[j])*(s[i]-s[j]);
while(l<r&&(Y(Q[r],k)-Y(Q[r-1],k))*(X(i)-X(Q[r]))>(Y(i,k)-Y(Q[r],k))*(X(Q[r])-X(Q[r-1])))r--;
Q[++r]=i;
}
}
printf("%lld",-s[n]*s[n]+f[n][m]*m);
return 0;
}
```
by reclusive @ 2023-09-12 09:06:14
如果不预处理的话，只能40分
by reclusive @ 2023-09-12 09:06:56