推出来式子然后斜率优化水过去就完事了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#define inf 0x3f3f3f3f
#define LL long long int
using namespace std;
const int maxn=; inline LL rd(){
LL x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N;
LL co[maxn],sm[maxn],f[maxn],L;
int q[maxn],h,t; inline LL pw2(LL x){return x*x;} inline bool judge1(int j1,int j2,int i){
return f[j1]+pw2(j1+sm[j1])-f[j2]-pw2(j2+sm[j2])<(*i+*sm[i]-*L-)*(j1+sm[j1]-j2-sm[j2]);
}
inline bool judge2(int j1,int j2,int j3){
return (f[j1]+pw2(j1+sm[j1])-f[j2]-pw2(j2+sm[j2]))*(j2+sm[j2]-j3-sm[j3])<
(f[j2]+pw2(j2+sm[j2])-f[j3]-pw2(j3+sm[j3]))*(j1+sm[j1]-j2-sm[j2]);
} int main(){
int i,j,k;
N=rd();L=rd();
for(i=;i<=N;i++)co[i]=rd(),sm[i]=sm[i-]+co[i];
h=t=;q[]=;
for(i=;i<=N;i++){
while(h<t&&!judge1(q[h],q[h+],i)) h++;
f[i]=f[q[h]]+pw2(i-q[h]-+sm[i]-sm[q[h]]-L);
while(h<t&&!judge2(q[t-],q[t],i)) t--;
q[++t]=i;
}printf("%lld\n",f[N]); return ;
}