记录编号	175707	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]玩具装箱toy	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.327 s
提交时间	2015-08-06 20:39:31	内存使用	1.44 MiB

/******************************************************************************
朴素方程：f[i]=f[k]+(i-k-1-L+s[i]-s[k])^2 (s数组为前缀和,将j+1~i放入一个容器中)
优化：设k>j且k优于j 
   则f[k]+(i-k-1-L+s[i]-s[k])^2<=f[j]+(i-j-1-L+s[i]-s[j])^2
   当i确定时，可以发现式中有许多常量，即O(1) 即可得出的与i有关的量
   设p=i+s[i]-L-1,则原式可化简为
      f[k]+(p-(s[k]+k))^2<=f[j]+(p-(s[j]+j))^2
   再化简
      f[k]+p^2-2*p*(s[k]+k)+(s[k]+k)^2<=f[j]+p^2-2*p*(s[j]+j)+(s[j]+j)^2 
      f[k]-2*p*(s[k]+k)+(s[k]+k)^2<=f[j]-2*p*(s[j]+j)+(s[j]+j)^2 
   移项，将常量移到一边，变量移到另一边
      f[k]-f[j]+(s[k]+k)^2-(s[j]+j)^2<=2*p*((s[j]+j)-(s[k]+k)) 
      f[k]-f[j]+(s[k]+k)^2-(s[j]+j)^2  /  ((s[k]+k)-(s[j]+j)) <=2*p
*********************************************************************************
   设i>j>k
      g[i,j]= f[i]-f[j]+(s[i]+i)^2-(s[j]+j)^2  /  ((s[i]+i)-(s[j]+j))
      g[j,k]同理 
   由上面得出若k>j 则当g[k,j]<=2*p(p=i-L-1+s[i])时  k优于j
   且我们发现，随着i的递增，p是单调不减的 。即对于i来说，若小于它的j不是最优解
   也就是存在k优于j，那么对于大于i的q来说，k也一定优于j，这就使得本题可以使用单调队列优化
   现在来讨论出队的条件
**********************************************************************************
   (1)g[k,j]<2*p (k>j) j可直接出队
   (2)g[i,k]<g[k,j](i>k>j)
       若g[i,k]<2*p    i优于k  k出队
       若g[i,k]>2*p    则g[k,j]>2*p   j比k优，k出队
   (3)g[i,k]>g[k,j] 
       g[k,j]>2*p j比k优
       g[k,j]<2*p g[i,j]无法确定，k不确定是否出队 
***********************************************************************************/
 
#include<cstdio>
 
using namespace std;
 
int n,l,q[100010];
long long f[50010],s[50010];
 
long long g(int x,int y)
{
     return f[x]-f[y]+(s[x]+x)*(s[x]+x)-(s[y]+y)*(s[y]+y);
}
 
long long a(int x,int y)
{
    return (s[x]+x)-(s[y]+y);
}
 
int main()
{
    freopen("bzoj_1010.in","r",stdin);
	freopen("bzoj_1010.out","w",stdout);
    scanf("%d%d",&n,&l);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&s[i]);
        s[i]+=s[i-1];
    }
    int head=0,tail=0;q[tail]=0;f[0]=0;
    for(int i=1;i<=n;i++)
    {
        long long p=i-l-1+s[i];
        while(head<=tail&&g(q[head+1],q[head])<2*p*a(q[head+1],q[head]))head++;
        f[i]=f[q[head]]+(p-s[q[head]]-q[head])*(p-s[q[head]]-q[head]);
        while(head<=tail&&g(q[tail],q[tail-1])*a(i,q[tail])>g(i,q[tail])*a(q[tail],q[tail-1]))tail--;q[++tail]=i;
    }
    printf("%lld",f[n]);
    //while(1);
}