记录编号	411785	评测结果	AAAAAAAAAA
题目名称	[APIO2010]特别行动队	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	1.094 s
提交时间	2017-06-06 17:44:27	内存使用	23.20 MiB

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