C++(g++ 7.5.0) 解法, 执行用时: 23ms, 内存消耗: 1340K, 提交时间: 2023-05-18 11:17:34

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
const int M=1e5;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
int n,L;
int l,r,que[N+5];
double dp[N+5],sum[N+5];
double A(int x){
	return sum[x]+x;
}
double B(int x){
	return sum[x]+x+L+1;
}
double slope(int x,int y){
	double val=(dp[y]+B(y)*B(y))-(dp[x]+B(x)*B(x));
	return val/(B(y)-B(x));
}
int main(){
    ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>L;
	for(int i=1;i<=n;i++){
		double x;cin>>x;
		sum[i]=sum[i-1]+x;
	}
	
	l=r=1;
	for(int i=1;i<=n;i++){
		while(l<r && slope(que[l],que[l+1])<2*A(i))l++;
		dp[i]=dp[que[l]]+(A(i)-B(que[l]))*(A(i)-B(que[l]));
		while(l<r && slope(que[r-1],i)<slope(que[r-1],que[r]))r--;
		que[++r]=i;
	}
	cout<<(long long)dp[n];
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 11ms, 内存消耗: 1036K, 提交时间: 2020-10-20 12:24:51

#include<bits/stdc++.h>
#define k(i,j) 1.0*(y[j]-y[i])/(x[j]-x[i])
using namespace std;
const int nn=51020;
int n,l,c,t,tt;
long long f,s,w,x[nn],y[nn];
int main(){
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++){
		scanf("%d",&c),s+=c+1,w=s-l-1;
		if(t>=tt)t=tt;
		else while(t<tt&&k(t,t+1)<(w<<1))t++;
		f=y[t]-2*w*x[t]+w*w,x[tt+1]=s,y[tt+1]=f+s*s;
		for(;tt&&k(tt-1,tt)>k(tt-1,tt+1);tt--)
			swap(x[tt],x[tt+1]),swap(y[tt],y[tt+1]);
		tt++;
	}return printf("%lld",f),0;
}