斜率优化求条玄关

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,L;
int dp[50010];
int c[50010];
int k[50010];
int cnt=0;
int check(int id){
	int idk=2*c[id]+2*L;
	int l=1,r=cnt;
	int ans=r;
	int mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(dp[k[mid+1]]+c[k[mid+1]]*c[k[mid+1]]-dp[k[mid]]-c[k[mid]]*c[k[mid]]>idk*(c[k[mid+1]]-c[k[mid]]))
			r=mid-1,ans=mid;
		else l=mid+1;
	}
	return k[ans];
}
signed main(){
	cin>>n>>L;
	L+=1;  
	for(int i=1,x;i<=n;i++){
		cin>>x;
		c[i]=c[i-1]+x+1;
		dp[i]=LLONG_MAX;
	}
	k[++cnt]=0;
	for(int i=1;i<=n;i++){
		int j=check(i);
		dp[i]=dp[j]+(c[i]-c[j]-L)*(c[i]-c[j]-L);
		while(cnt>1 and (dp[k[cnt]]+c[k[cnt]]*c[k[cnt]]-dp[k[cnt-1]]-c[k[cnt-1]]*c[k[cnt-1]])*(c[i]-c[k[cnt]])>=(dp[i]+c[i]*c[i]-dp[k[cnt]]-c[k[cnt]]*c[k[cnt]])*(c[k[cnt]]-c[k[cnt-1]]))--cnt;
		k[++cnt]=i;
	}	
	cout<<dp[n];
	return 0;
}