记录编号	250245	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 征途	最终得分	100
用户昵称	bhiaibogf	是否通过	通过
代码语言	C++	运行时间	0.380 s
提交时间	2016-04-14 19:20:36	内存使用	0.38 MiB

#include <bits/stdc++.h>
using namespace std;

const int MAXN=3000+5;
int q[MAXN],s[MAXN];
long long f[2][MAXN];
int read(){
	int r=0;char c;
	while(!isdigit(c=getchar()));
	while(r=r*10+c-'0',isdigit(c=getchar()));
	return r;
}

int sqr(int x) {return x*x;}
double slop(int k,int i,int j){
	return 1.0*(f[k][i]-f[k][j]+sqr(s[i])-sqr(s[j]))/(s[i]-s[j]);
}

int main(){
#ifdef bhiaibogf
	freopen("in.in","r",stdin);
#else
	freopen("menci_journey.in","r",stdin);
	freopen("menci_journey.out","w",stdout);
#endif
	int n=read(),m=read();
	//for(int i=1;i<=n;i++) cout<<(s[i]=read()+s[i-1],i)<<endl;
	for(int i=1;i<=n;i++)
		scanf("%d",&s[i]),s[i]+=s[i-1];
	memset(f[0],0x3f,sizeof f[0]);//第一次只能从1到j...
	f[0][0]=0;
	for(int i=1;i<=m;i++){
		int cur=i&1,las=cur^1;
		int l=0,r=1;
		for(int j=1;j<=n;j++){
			while(r-l>=2 && slop(las,q[l],q[l+1])<2*s[j]) l++;
			int k=q[l];
			f[cur][j]=f[las][k]+sqr(s[j]-s[k]);
			while(r-l>=2 && slop(las,q[r-1],j)<slop(las,q[r-2],q[r-1])) r--;
			q[r++]=j;
		}
	}
	cout<<f[m&1][n]*m-sqr(s[n])<<endl;
	return 0;
}