bzoj 1010: [HNOI2008]玩具装箱toy

/**************************************************************
    Problem: 1010
    User: lxy8584099
    Language: C++
    Result: Accepted
    Time:188 ms
    Memory:1800 kb
****************************************************************/
 
/*
    斜率优化
    令 A(i) = sum[i] + i
    令 b(i) = sum[i] + i + L + 1
    若 j 比 k 更优
    有 2*A(i) > ( f(j)-f(k)+B(j)^2-B(k)^2 ) / ( B(j)-B(k) ) 
    A(i) 为正 递增  凸包下凸 
    注意 队列的l,r 初始值要相同 而不是r=l-1 
    因为要留一个位置给0  前i个装在一起 
*/
#include<cstdio>
#define db double
#define ll long long
#define A(i) (sum[i]+i)
#define B(i) (sum[i]+i+L+1)
#define sqr(x) ((x)*(x))
using namespace std;
const int N=50050;
int q[N],l=0,r=0,n,L;
ll f[N],sum[N];
db xl(int i,int j)
{
    return (db)(f[i]+sqr(B(i))-f[j]-sqr(B(j))) / (db)(B(i)-B(j)) ;
}
int main()
{
    scanf("%d%d",&n,&L);
    for(int i=1,x;i<=n;i++) scanf("%d",&x),sum[i]=sum[i-1]+x;
    for(int i=1;i<=n;i++)
    {
        while(l<r&&xl(q[l],q[l+1])<=2*A(i)) l++;
        f[i]=f[q[l]]+sqr(A(i)-B(q[l]));
        while(l<r&&xl(q[r-1],q[r])>xl(q[r-1],i)) r--;
        q[++r]=i;
    }
    printf("%lld",f[n]);
    return 0;
}