记录编号	345196	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]玩具装箱toy	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.176 s
提交时间	2016-11-10 21:04:25	内存使用	1.31 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define g(i) ( i + s[i] - L ) 
#define x(i) ( i + s[i-1] )
#define y(i) ( f[i-1] + x(i) * x(i) ) 
#define T(j1,j2) ( ( y(j2) - y(j1) ) / ( x(j2) - x(j1) ) )
#define size (q.size())
#define d1 q[size-1]
#define d2 q[size-2]
#define q1 q[0]
#define q2 q[1]
using namespace std;
const int maxn = 50000 + 10 ;
typedef long long ll;
ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
ll N,L,a[maxn],s[maxn],f[maxn];
deque<int> q;
ll Dp(){
	for(int i = 1 ; i <= N ; i ++ ) {
		while( size > 1 && T(d2,d1) > T(d1,i) )q.pop_back();
		q.push_back(i);
		while( size > 1 && T(q1,q2) < 2 * g(i) )q.pop_front();
		f[i] = f[q1-1] + ( g(i) - x(q1) ) * ( g(i) - x(q1) ) ;
	}
	return f[N];
}
int main(){
	freopen("bzoj_1010.in","r",stdin); 
	freopen("bzoj_1010.out","w",stdout);
	N = read() ; L = read() ;
	for( int i = 1 ; i <= N	 ;i ++ ) {
		a[i] = read() ;
		s[i] = s[i-1] + a[i] ;
	}
	printf("%lld\n",Dp());
}