文件详细信息

下载本文件

本文件的大小为 737 字节。

#include<cstdio>
typedef long long ll;
int read(){
	int ch=getchar(),num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num;
}
const int maxn=50005;
int n,L;
ll f[maxn],dp[maxn];
int h=1,t,q[maxn];
ll up(int k,int j){
	return dp[j]-dp[k]+(f[j]+L)*(f[j]+L)-(f[k]+L)*(f[k]+L);
}
ll down(int k,int j){
	return(f[j]-f[k])<<1;
}
int main(){
	n=read(),L=read()+1;
	for(int i=1;i<=n;i++)f[i]=f[i-1]+read()+1;
	q[++t]=0;
	for(int i=1;i<=n;i++){
		while(h<t&&up(q[h],q[h+1])<=f[i]*down(q[h],q[h+1]))h++;
		dp[i]=dp[q[h]]+(f[i]-f[q[h]]-L)*(f[i]-f[q[h]]-L);
		while(h<t&&up(q[t],i)*down(q[t-1],q[t])<up(q[t-1],q[t])*down(q[t],i))t--;
		q[++t]=i;
	}
	printf("%lld",dp[n]);
	return 0;
}