记录编号	174627	评测结果	AAAAAAAAAA
题目名称	1330.[HNOI 2008]玩具装箱toy	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.124 s
提交时间	2015-08-02 06:18:47	内存使用	10.58 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
long long n,l,sum[500002],dp[500002],q[500002];
int h,tail,head;
long long getsum(int i,int j){
	return (sum[i]-sum[j]+i-j-1-l)*(sum[i]-sum[j]+i-j-1-l);
}
long long getup(int i,int j){
	return dp[i]+(sum[i]+i)*(sum[i]+i)-(dp[j]+(sum[j]+j)*(sum[j]+j));
}
long long getdown(int i,int j){
	return (sum[i]+i)-(sum[j]+j);
}
int main(){
	freopen("bzoj_1010.in","r",stdin);
	freopen("bzoj_1010.out","w",stdout);
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;++i){
		scanf("%d",&h);
		sum[i]=sum[i-1]+h;
	}
	tail=head=0;
	dp[0]=sum[0]=0;
	q[tail++]=0;
	for(int i=1;i<=n;++i){
		int rt=sum[i]+i-l-1;
		while(tail>head+1&&getup(q[head+1],q[head])<=2*rt*getdown(q[head+1],q[head]))
		   head++;
		dp[i]=dp[q[head]]+getsum(i,q[head]);
		while(tail>head+1&&getup(i,q[tail-1])*getdown(q[tail-1],q[tail-2])<=getup(q[tail-1],q[tail-2])*getdown(i,q[tail-1]))
		   tail--;
		q[tail++]=i;
	}
   printf("%lld",dp[n]);
}