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

#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;
}