记录编号	61717	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]玩具装箱toy	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.079 s
提交时间	2013-06-15 14:05:54	内存使用	1.17 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<deque>
#include<iomanip>
using namespace std;
typedef long long ll;
const ll SIZEN=50001,INF=0x7fffffff;
ll S[SIZEN]={0};//S[i]=到i的前缀和+i
ll g[SIZEN]={0};
ll f[SIZEN]={0};
ll N,L,C;
ll sqr(ll x){
	return x*x;
}
ll fig(ll x,ll i){//状态x下决策i的值
	return f[i]+sqr(g[x]-S[i]);
}
ll CX(ll x){
	return g[x];
}
ll CY(ll x){
	return f[x]+sqr(S[x]);
}
bool uper(ll x,ll y,ll z){//z在线段xy上方,确保横坐标x<z<y
	double x1,y1,x2,y2;
	x1=CX(y)-CX(x),y1=CY(y)-CY(x);
	x2=CX(z)-CX(x),y2=CY(z)-CY(x);
	return x2*y1<=y2*x1;
}
class MNQ{
public:
	deque<ll> lis;
	void clf(ll x){//维护队首
		while(lis.size()>1&&fig(x,lis[0])>=fig(x,lis[1])) lis.pop_front();
	}
	ll front(ll x){//在状态x下返回最优决策
		clf(x);
		return lis[0];
	}
	bool sol(ll x){//队尾点应该被删除
		ll back=lis.size()-1;
		return uper(lis[back-1],x,lis[back]);
	}
	void clb(ll x){//新入队决策x并维护队尾
		while(lis.size()>1&&sol(x))	lis.pop_back();
	}
	void push_back(ll x){
		clb(x);
		lis.push_back(x);
	}
}Q;
void process(void){
	Q.push_back(0);
	ll i;
	for(i=1;i<=N;i++){
		f[i]=fig(i,Q.front(i));
		Q.push_back(i);
	}
	printf("%lld\n",f[N]);
}
void init(void){
	scanf("%lld%lld",&N,&L);
	C=L+1;
	ll i;
	for(i=1;i<=N;i++){
		scanf("%lld",&S[i]);
		S[i]+=S[i-1];
	}
	for(i=1;i<=N;i++) S[i]+=i;
	g[0]=-INF;
	for(i=1;i<=N;i++) g[i]=S[i]-C;
}
int main(){
	freopen("bzoj_1010.in","r",stdin);
	freopen("bzoj_1010.out","w",stdout);
	init();
	process();
	return 0;
}