记录编号	481450	评测结果	AAAAAAAWAW
题目名称	[APIO2010]特别行动队	最终得分	80
用户昵称	Ryzen	是否通过	未通过
代码语言	C++	运行时间	1.784 s
提交时间	2018-01-02 21:28:47	内存使用	46.09 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,a,b,c,x[N],sum[N],f[N],t[N],g[N],q[N],l=0,r=0;
int calc(int i,int j){
    return (g[i]-g[j])/(2*a*(sum[i]-sum[j]));
}
main(){
    freopen("special.in","r",stdin);
    freopen("special.out","w",stdout);
    cin>>n>>a>>b>>c;
    for(int i=1;i<=n;i++)cin>>x[i],sum[i]=sum[i-1]+x[i],t[i]=sum[i]*sum[i]-b*sum[i];
    for(int i=1;i<=n;i++){
	while(l<r&&calc(q[l],q[l+1])<=sum[i])l++;
	int j=q[l];
	f[i]=f[j]+a*(sum[i]-sum[j])*(sum[i]-sum[j])+b*(sum[i]-sum[j])+c;
	g[i]=f[i]+t[i];
	while(l<r&&calc(q[r],i)<=calc(q[r-1],q[r]))r--;
	q[++r]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}