记录编号	373156	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]玩具装箱toy	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.084 s
提交时间	2017-02-20 10:43:05	内存使用	2.01 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50010;
const double eps=1e-7;
double getk(int,int);
long long f[maxn],s[maxn],x[maxn],y[maxn];
int n,L,q[maxn],l=0,r=0;
int main(){
	freopen("bzoj_1010.in","r",stdin);
	freopen("bzoj_1010.out","w",stdout);
	scanf("%d%d",&n,&L);
	L++;
	for(int i=1;i<=n;i++){
		scanf("%lld",&s[i]);
		s[i]+=s[i-1]+1;
		x[i]=s[i];
	}
	q[0]=0;
	for(int i=1;i<=n;i++){
		while(l<r&&getk(q[l],q[l+1])-eps<s[i]*2)l++;
		f[i]=f[q[l]]+(s[i]-s[q[l]]-L)*(s[i]-s[q[l]]-L);
		y[i]=f[i]+s[i]*s[i]+2*s[i]*L;//printf("i=%d s=%d j=%d f=%d x=%d y=%d\n",i,(int)s[i],q[l],(int)f[i],(int)x[i],(int)y[i]);
		while(l<r&&getk(q[r-1],q[r])+eps>getk(q[r],i))r--;
		q[++r]=i;
		//printf("q:");for(int i=l;i<=r;i++)printf(" %d",q[i]);printf("\n");
	}
	printf("%lld",f[n]);
	return 0;
}
double getk(int i,int j){return (double)(y[i]-y[j])/(x[i]-x[j]);}