记录编号	231146	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]玩具装箱toy	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.129 s
提交时间	2016-02-25 16:06:30	内存使用	2.22 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
const int SIZEN=50010;
typedef long long LL;
int N,L;
LL c[SIZEN];
deque<int> Q;
void read()
{
	scanf("%d%d",&N,&L);
	for(int i=1;i<=N;i++) scanf("%d",&c[i]);
}
LL x[SIZEN],y[SIZEN],g[SIZEN];
LL f[SIZEN];
void work()
{
	c[0]=0;
	for(int i=1;i<=N;i++) c[i]=c[i-1]+c[i];
	for(int i=1;i<=N;i++)
	{
		g[i]=i+c[i]-L;
		x[i]=i+c[i-1];y[i]=f[i-1]+x[i]*x[i];
		while(Q.size()>1&&(y[i]-y[Q[Q.size()-1]])*(x[Q[Q.size()-1]]-x[Q[Q.size()-2]])<(y[Q[Q.size()-1]]-y[Q[Q.size()-2]])*(x[i]-x[Q[Q.size()-1]])) Q.pop_back();
		Q.push_back(i);
		while(Q.size()>1&&(y[Q[1]]-y[Q[0]])<2*g[i]*(x[Q[1]]-x[Q[0]])) Q.pop_front();
		int j=Q[0];
		f[i]=f[j-1]+(g[i]-x[j])*(g[i]-x[j]);
	}
	printf("%lld",f[N]);
}
int main()
{
	freopen("bzoj_1010.in","r",stdin);
	freopen("bzoj_1010.out","w",stdout);
	read();
	work();
	return 0;
}