题目链接

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=51000;
ll a[maxn],b[maxn],dp[maxn],sum[maxn],q[maxn];
ll n,L;
double fi(int i,int j)
{
return (dp[j]+b[j]*b[j]-(dp[i]+b[i]*b[i]))*1.0/(b[j]-b[i]);
}
int main(void)
{
scanf("%lld%lld",&n,&L);
for(int i=1;i<=n;i++)
{
scanf("%lld",&sum[i]);
sum[i]+=sum[i-1];
a[i]=sum[i]+i;
b[i]=sum[i]+i+L+1;
}
b[0]=L+1;
int l=1,r=1;
q[1]=0;
for(int i=1;i<=n;i++)
{
while(l<r&&fi(q[l],q[l+1])<=a[i]*2) l++;
int now=q[l];
dp[i]=dp[now]+(a[i]-b[now])*(a[i]-b[now]);
while(l<r&&fi(q[r-1],q[r])>=fi(q[r-1],i)) r--;
q[++r]=i;
}
printf("%lld\n",dp[n]);
return 0;
}