记录编号	156045	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]玩具装箱toy	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.148 s
提交时间	2015-04-01 19:09:42	内存使用	1.46 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
const double eps=1e-10;
///==============struct declaration==============

///==============var declaration=================
const int MAXN=60010;
int n,L,tail=1,front=1;
int q[MAXN];
long long dp[MAXN],c[MAXN];
///==============function declaration============
long long sqr(long long x){return x*x;}
double g(int i,int j){return double(dp[i]-dp[j]+sqr(c[i])-sqr(c[j])+2*(long long)L*(c[i]-c[j]))/double(2*c[i]-2*c[j]);}
///==============main code=======================
int main()
{
	//#define FILE__
	//#ifdef FILE__
   freopen("bzoj_1010.in","r",stdin);
   freopen("bzoj_1010.out","w",stdout);
	//#endif 
	scanf("%d%d",&n,&L);L++;
	for(int i=1;i<=n;i++){
		scanf("%lld",c+i);
		c[i]+=c[i-1];
	}
	for(int i=1;i<=n;i++)
		c[i]+=i;
	q[1]=0;dp[0]=0;
	for(int i=1;i<=n;i++){
		while (front<tail&&g(q[front+1],q[front])<c[i])
			front++;
		dp[i]=dp[q[front]]+sqr(c[i]-c[q[front]]-L);
		while (front<tail&&g(q[tail-1],q[tail])>g(q[tail],i))
			tail--;
		q[++tail]=i;
	}
	//	for(int i=1;i<=n;i++)
		//		printf("%lld\n",dp[i]);
	printf("%lld\n",dp[n]);
   return 0;
}
///================fuction code====================