记录编号	345313	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]玩具装箱toy	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.135 s
提交时间	2016-11-10 22:16:11	内存使用	1.44 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=50010;
typedef long long ll;
int n,c[N],q[N],head,tail;
ll l,dp[N],sum[N];
ll V(ll x){return (l-x)*(l-x);}
ll F(int x){return sum[x]+x;}
double k(int j,int k){
	return 1.0*(dp[j]-dp[k])/(F(j)-F(k))+F(j)+F(k);
}
int main()
{
	freopen("bzoj_1010.in","r",stdin);
	freopen("bzoj_1010.out","w",stdout);
	scanf("%d%lld",&n,&l);
	q[head=tail=1]=0;
	for (int i=1;i<=n;i++){
		scanf("%d",&c[i]);
		sum[i]=sum[i-1]+c[i];
		for (;head<tail&&k(q[head],q[head+1])<=2*(F(i)-1-l);head++);
		int j=q[head];
		dp[i]=dp[j]+V(F(i)-F(j)-1);
		for (;head<tail&&k(q[tail-1],q[tail])>k(q[tail],i);tail--);
		q[++tail]=i;
	}
	printf("%lld\n",dp[n]);
	return 0;
}