斜率优化

///斜率优化

///对于dp[i]=max/min(f(j)+g(j)*h(i)+H(i))形式

///为简化描述我们可以只考虑min情况
///我们对式子中不同的j作差
///这里姑且用j与k表示
///不妨设k>j
///得到差f(k)-f(j)+h(i)*(g(k)-g(j))

///如果k优于j那么上式<=0
///f(k)-f(j)+h(i)*(g(k)-g(j))<=0
///如果g函数满足单调，为了方便 我们假设他单调增
///则【f(k)-f(j)】/【g(k)-g(j)】<=h(i)
///斜率找到，就是最大且小于h(i)的一组相邻点的斜率，这时的右端点就是dp转移式所要的东西

///总而言之，当且仅当转移方程满足dp[i]=max/min(f(j)+g(j)*h(i)+H(i))形式且g函数单调
///我们就可以斜率优化 

///重在思维与推导，不在板子，此板子仅供参考
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=5e4;
long long Q[maxn],dp[maxn],s[maxn];

long long f(int j)
{
    return dp[j]+(j+s[j])*(j+s[j]);
}
double Slope(long long j,long long k)   //求斜率
{
    return double(f(k)-f(j))/(k+s[k]-j-s[j]);
}

int main()
{
    ll n,L;
    while(~scanf("%lld%lld",&n,&L))
    {
        for(int i=1; i<=n; i++)
        {
            int tmp;
            scanf("%d",&tmp);
            s[i]=s[i-1]+tmp;
        }

        int Left=1,Right=1;
        Q[1]=0;
        dp[0]=0;
        for(int i=1; i<=n; i++)
        {
            while(Left<Right&&Slope(Q[Left],Q[Left+1])<=2*(s[i]+i-L-1))
                Left++; //维护队首（删除非最优决策）
            int j=Q[Left];
            dp[i]=dp[j]+(i-j-1+s[i]-s[j]-L)*(i-j-1+s[i]-s[j]-L); //计算当前f
            while(Left<Right&&Slope(Q[Right-1],Q[Right])>=Slope(Q[Right],i))
                Right--; //维护队尾（维护下凸包性质）
            Q[++Right]=i; //入队
        }
        printf("%lld\n",dp[n]);
    }
    return 0;
}
///solved pzoj 1010