李超线段树 0pts 求调

#include <bits/stdc++.h>
#define fin(str) freopen(str,"r",stdin)
#define fout(str) freopen(str,"w",stdout)
#define ll long long
#define bint __int128
using namespace std;

const int maxn=5e4+5;
const bint INF=1e36;

int n,a[maxn];
bint L,s[maxn];

namespace LCSGT{
	#define RANGE 1,(ll)1e16
	struct segment{
		int lc,rc;
		bint k,b;
	}c[maxn<<5];
	int tot;
	inline int addNode(){
		c[++tot]=(segment){0,0,INF,INF};
		return tot;
	}
	inline void update(int rt,ll l,ll r,bint k,bint b){
		if (c[rt].k==INF && c[rt].b==INF){
			c[rt].k=k,c[rt].b=b;
			return ;
		}
		ll mid=(l+r)>>1;
		bint mid0=c[rt].k*mid+c[rt].b,mid1=k*mid+b;
		if (mid0>=mid1){
			swap(c[rt].k,k);
			swap(c[rt].b,b);
		}
		bint l0=c[rt].k*l+c[rt].b,l1=k*l+b;
		bint r0=c[rt].k*r+c[rt].b,r1=k*r+b;
		if (l0<=l1 && r0>=r1){
			if (!c[rt].rc) c[rt].rc=addNode();
			update(c[rt].rc,mid+1,r,c[rt].k,c[rt].b);
		}else if (l0>=l1 && r0<=r1){
			if (!c[rt].lc) c[rt].lc=addNode();
			update(c[rt].lc,l,mid,c[rt].k,c[rt].b);
		}
		c[rt].k=k,c[rt].b=b;
	}
	inline bint query(int rt,ll l,ll r,ll pos){
		if (c[rt].k==INF && c[rt].b==INF) return INF;
		ll mid=(l+r)>>1;
		bint res=c[rt].k*pos+c[rt].b;
		if (pos<=mid && c[rt].lc) res=min(res,query(c[rt].lc,l,mid,pos));
		if (pos>mid && c[rt].rc) res=min(res,query(c[rt].rc,mid+1,r,pos));
		return res;
	}
}
using namespace LCSGT;

bint F[maxn];

inline bint rd(){
	bint x=0; char ch=getchar();
	while (ch<'0' || ch>'9') ch=getchar();
	while (ch>='0' && ch<='9'){
		x=(x<<3)+(x<<1)+(ch-'0');
		ch=getchar();
	}
	return x;
}
inline bint write(bint x){
	if (x>9) write(x/10);
	putchar('0'+x%10);
}

int main(){
//	fin("data.in");
//	fout("data.out");
	scanf("%d",&n),L=rd()+1;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
	
	addNode();
	update(1,RANGE,0,0);
	
	for (int i=1;i<=n;i++){
		F[i]=((bint)(i+s[i]-L))*(i+s[i]-L)+query(1,RANGE,s[i]+i);
		update(1,RANGE,(s[i]+i)*-2,F[i]+((bint)(s[i]+i))*(s[i]+i)+L*(s[i]+i)*2);
	}
	
	cerr<<tot<<'\n';
	
//	for (int i=1;i<=n;i++) write(F[i]),putchar('\n');
	write(F[n]);
	
	return 0;
}