记录编号	405993	评测结果	RRRRRRRRRR
题目名称	[HZOI 2016]在路上	最终得分	0
用户昵称	Hzoi_Hugh	是否通过	未通过
代码语言	C++	运行时间	0.004 s
提交时间	2017-05-17 18:25:02	内存使用	38.44 MiB

#include<cstdio>
using namespace std;
long long a,b,c,s[1000001],f[1000001];
long long g[1000001];
long long n,h[1000001];
long long q[1000001],head,tail;
int main()
{
    freopen("special.in","r",stdin);
	freopen("special.out","w",stdout);
    scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
    for(int i=1;i<=n;i++)
    {
      scanf("%lld",&s[i]);
      s[i]+=s[i-1];
      h[i]=(long long)(2*a*s[i]);
      while(head<tail&&(double)(g[q[head]]-g[q[head+1]])/(h[q[head]]-h[q[head+1]])<s[i])head++;
      long long sum=s[i]-s[q[head]];
      f[i]=(long long)(f[q[head]]+a*sum*sum+b*sum+c);
      g[i]=(long long)(f[i]+a*s[i]*s[i]-b*s[i]);
      while(head<tail&&(g[q[tail]]-g[i])/(h[q[tail]]-h[i])<(g[q[tail]]-g[q[tail-1]])/(h[q[tail]]-h[q[tail-1]]))tail--;
      q[++tail]=i;
    }
    printf("%lld",f[n]);
    return 0;
}