P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为 1⋯N1\cdots N1⋯N 的 NNN 件玩具，第 iii 件玩具经过压缩后变成一维长度为 CiC_iCi .为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第 iii 件玩具到第 jjj 个玩具放到一个容器中，那么容器的长度将为 x=j−i+∑k=ijCkx=j-i+\sum\limits_{k=i}^{j}C_kx=j−i+k=i∑jCk 制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 xxx ,其制作费用为 (X−L)2(X-L)^2(X−L)2 .其中 LLL 是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 LLL 。但他希望费用最小.

输入输出格式

输入格式：

 

第一行输入两个整数N，L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7

 

输出格式：

 

输出最小费用

 

输入输出样例

输入样例#1：

5 434214 输出样例#1：

1 题解 　　 　　

1 // luogu-judger-enable-o2 2 //minamoto 3 #include
       
         4 #include
        
          5 #include
         
           6 #define db double 7 #define ll long long 8 using namespace std; 9 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)10 char buf[1<<21],*p1=buf,*p2=buf;11 inline int read(){12     #define num ch-'0'13     char ch;bool flag=0;int res;14     while(!isdigit(ch=getc()))15     (ch=='-')&&(flag=true);16     for(res=num;isdigit(ch=getc());res=res*10+num);17     (flag)&&(res=-res);18     #undef num19     return res;20 }21 const int N=50005;22 int n,L;23 db sum[N],dp[N];int h,t,q[N];24 inline db a(int i){
     return sum[i]+i;}25 inline db b(int i){
     return sum[i]+i+L+1;}26 inline db X(int i){
     return b(i);}27 inline db Y(int i){
     return dp[i]+b(i)*b(i);}28 inline db slope(int i,int j){
     return (Y(i)-Y(j))/(X(i)-X(j));}29 int main(){30     //freopen("testdata.in","r",stdin);31     n=read(),L=read();32     for(int i=1;i<=n;++i) sum[i]=read()+sum[i-1];33     h=t=1;34     for(int i=1;i<=n;++i){35         while(h
          
           <2*a(i)) ++h;36         double p=a(i)-b(q[h]);37         dp[i]=dp[q[h]]+p*p;38         while(h
           
            slope(q[t-1],i)) --t;39         q[++t]=i;40     }41     printf("%lld\n",(ll)dp[n]);42     return 0;43 }