记录编号	141755	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]玩具装箱toy	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.051 s
提交时间	2014-12-03 22:37:18	内存使用	1.63 MiB

#include <cctype>
#include <cstdio>
using namespace std;
template<typename T>inline void getd(T &x){
	char c = getchar(); bool minus = 0;
	while(!isdigit(c) && c != '-')c = getchar();
	if(c == '-')minus = 1, c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 + c - '0';
	if(minus)x = -x;
}
/*========================================================*/
typedef long long LL;
const int maxn = 50003;
int N, L, V[maxn], it1 = 0, it2 = 1;
LL S, X[maxn], Y[maxn], f[maxn];
#define cmp(x, y, j, k)\
	(y<=Y[j])?1:((k<0)?0:((x-X[j])*(Y[j]-Y[k]) >= (X[j]-X[k])*(y-Y[j])))

inline void insert(LL x, LL y){
	if(it2 <= it1+1){
		X[it2] = x, Y[it2] = y;
		++it2;
		return;
	}
	while(it2 > it1 && cmp(x, y, it2-1, it2-2))--it2;
	X[it2] = x, Y[it2] = y;
	++it2;
}
inline void dp(){
	int i;
	LL k, t, b1, b2, y;
	for(i = 1;i <= N;++i){
		S += V[i];
		t = S - L - 1, k = - t << 1;
		b2 = k * X[it1] + Y[it1];
		if(it2 - it1 <= 1){
			f[i] = t * t + b2;
			y = f[i] + S * S;
			insert(S, y);
			continue;
		}
		while(it1 + 1 < it2){
			b1 = b2, b2 = k * X[it1+1] + Y[it1+1];
			if(b1 >= b2)++it1;
			else break;
		}
		f[i] = t * t + k * X[it1] + Y[it1];
		y = f[i] + S * S;
		insert(S, y); 
	}
	printf("%lld\n", f[N]);
}
int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	#else
	freopen("bzoj_1010.in", "r", stdin);
	freopen("bzoj_1010.out", "w", stdout);
	#endif
	int i, C;
	getd(N), getd(L);
	for(i = 1;i <= N;++i)
		getd(C), V[i] = C + 1;
	dp();
	return 0;
}