记录编号	592647	评测结果	AAAAAAAAAA
题目名称	[APIO2010]特别行动队	最终得分	100
用户昵称	qyd	是否通过	通过
代码语言	C++	运行时间	1.163 s
提交时间	2024-07-26 21:06:41	内存使用	14.74 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000010;
int n,a,b,c;
ll s[maxn],dp[maxn];
ll head,tail,q[maxn];
ll t(int i){return dp[i]-a*s[i]*s[i]-b*s[i]-c;}//intercept
ll k(int i){return 2*a*s[i];}//slope
ll x(int i){return s[i];}//coordinate-x
ll y(int i){return dp[i]+a*s[i]*s[i]-b*s[i];}//coodinate-y
double slope(int i,int j){return 1.0*(y(j)-y(i))/(x(j)-x(i));}
//to calculate the slope between Pi and Pj
int main()
{
	freopen("special.in","r",stdin);
	freopen("special.out","w",stdout);
	
	cin>>n>>a>>b>>c;
	s[0]=0;dp[0]=0;q[0]=0;
	for(int i=1;i<=n;i++)
	{cin>>s[i];s[i]+=s[i-1];}
	head=0,tail=0;
	
	for(int i=1;i<=n;i++)
	{
		while(head<tail&&slope(q[head],q[head+1])>k(i))head++;
		dp[i]=y(q[head])-k(i)*x(q[head])+a*s[i]*s[i]+b*s[i]+c;
		while(head<tail&&slope(q[tail-1],q[tail])<slope(q[tail-1],i))tail--;
		q[++tail]=i;
	}
	cout<<dp[n]<<endl;
	return 0;
}