设 $dp(i)$ 表示前 $i$ 个玩具的答案。则有转移：

$$dp(i)=\min_{0\leq j < i}\left[dp(j)+\left(\sum_{k=j+1}^ic_k+i-(j+1)-L\right)^2\right]. $$

设 $s_i$ 是 $c_i$ 的前缀和，$x_i=s_i+i$，则有 $dp(i)=\min\limits_{0\leq j < i}\left[dp(j)+(x_i-x_j-1-L)^2\right]$。

对于 $j_1 < j_2$，若从 $j_2$ 转移比 $j_1$ 优秀，则有

$$dp(j_1)+(x_i-x_{j_1}-L-1)^2 \geq dp(j_2)+(x_i-x_{j_2}-L-1)^2. $$

拆开可得 $\left[dp(j_2)+(x_{j_2}+L+1)^2\right]-\left[dp(j_1)+(x_{j_1}+L+1)^2\right] \leq 2x_i(x_{j_2}-x_{j_1})$。

记 $y_i=dp(i)+(x_i+L+1)^2$，则上式等价于 $\dfrac{y_{j_2}-y_{j_1}}{x_{j_2}-x_{j_1}} \leq 2x_i$。

可以把 $(x_i,y_i)$ 看作平面上的点，维护一个单调升的队列即可。

时间复杂度 $\Theta(n)$。

/**
 * @date: 2024.04.06
 * @problem: P3195, BZOJ1010
 * @tags: 动态规划, 斜率优化
 */

#include<bits/stdc++.h>
using namespace std;

int n,l;
long long c[50001],x[50001],y[50001],dp[50001];
int q[50001],head,tail;

inline double slope(int u,int v){
    return (y[v]-y[u])*1.0/(x[v]-x[u]);
}

int main(){
    scanf("%d%d",&n,&l);
    for(int i=1;i<=n;i++)
        scanf("%lld",c+i),c[i]+=c[i-1];
    x[0]=0,y[0]=(l+1ll)*(l+1);
    for(int i=1;i<=n;i++){
        x[i]=c[i]+i;
        while(head<tail&&slope(q[head],q[head+1])<=2*x[i])head++;
        dp[i]=dp[q[head]]+(x[i]-x[q[head]]-l-1)*(x[i]-x[q[head]]-l-1);
        y[i]=(x[i]+l+1)*(x[i]+l+1)+dp[i];
        while(head<tail&&slope(q[tail],i)<slope(q[tail-1],q[tail]))tail--;
        q[++tail]=i;
    }
    printf("%lld\n",dp[n]);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e4+5;
int n,L;
LL a[N],sum[N],f[N];
int l,r,Q[N];
double X(int j){
	return 1.0*(j+sum[j]);
}
double Y(int j){
	return 1.0*(f[j]+(j+sum[j])*(j+sum[j])+2*(j+sum[j])*(L+1));
}
double slop(int j1,int j2){
	if(X(j2)==X(j1))return 1e18*(Y(j2)-Y(j1));
	return (Y(j2)-Y(j1))/(X(j2)-X(j1));
}
int main(){
	scanf("%d%d",&n,&L);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	l=1,r=1;Q[l]=0;
	for(int i=1;i<=n;i++){
		while(l<r&&slop(Q[l],Q[l+1])<=2.0*(i+sum[i]))l++;
		int j=Q[l];
		f[i]=f[j]+(i-j-L-1+sum[i]-sum[j])*(i-j-L-1+sum[i]-sum[j]);
		while(l<r&&slop(Q[r],i)<=slop(Q[r-1],Q[r]))r--;
		Q[++r]=i;
	}
	printf("%lld",f[n]);
	return 0;
}