记录编号	250558	评测结果	AAAAAAAAWW
题目名称	[SDOI 2016 Round1] 征途	最终得分	80
用户昵称	zys	是否通过	未通过
代码语言	C++	运行时间	0.379 s
提交时间	2016-04-15 11:50:37	内存使用	93.79 MiB

/*
    设 v 为平均数
    方差:  ((x1-v)^2+(x2-v)^2+...(x^m-v)^2)/m
		 =  (m*v^2+x1^2-2*x1^v+x2^2-2*x2*v+....xm^2-2*xm*v)/m
         乘以m^2得
			m^2*v^2+m*(x1^2-2*x1^v+x2^2-2*x2*v+....xm^2-2*xm*v)
*/
#define maxn 3500
#define eps 1e-14

#include<cstdio>
#include<algorithm>

using namespace std;

int n,m,pre[maxn];
double ave,sum[maxn],res,f[maxn][maxn];

inline double cal(int l,int r)
{
	return (sum[r]-sum[l-1])*(sum[r]-sum[l-1])-2.0*ave*(sum[r]-sum[l-1]);
}

void solve(double *f,double *g,int l,int r,int L,int R)
{
	if(l>r)return;
	int mid=(l+r)>>1,pos=0;g[mid]=1e12;
	for(int i=L;i<=min(mid-1,R);i++){
		double p=f[i]+cal(i+1,mid);
		if(p+eps<g[mid])g[mid]=p,pos=i;
	}
	solve(f,g,l,mid-1,L,pos);
	solve(f,g,mid+1,r,pos,R);
}

inline void read()
{
	scanf("%d%d",&n,&m);
	for(int i=1,l;i<=n;i++)
		scanf("%d",&l),sum[i]=sum[i-1]+l;
	ave=sum[n]/m;
}

inline void solve()
{
	for(int i=1;i<=n;i++)f[1][i]=cal(1,i);
	for(int i=2;i<=m;i++)solve(f[i-1],f[i],i,n,i-1,n-1);
	printf("%0.0lf",f[m][n]*m+ave*ave*m*m);
}

int main()
{
    freopen("menci_journey.in","r",stdin);
	freopen("menci_journey.out","w",stdout);
	read();solve();
}