记录编号	345351	评测结果	AAAAAAAAAA
题目名称	[APIO2010]特别行动队	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	1.068 s
提交时间	2016-11-11 06:00:39	内存使用	23.20 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const ll maxn = 1000005;
int N;
ll a, b, c;
ll s[maxn], f[maxn];
ll q[maxn], hd, tl;
inline ll tu(ll x){ return x*x; }
inline ll h(int i){ return 2*a*s[i]; }
inline ll x(int j){ return s[j-1]; }
inline ll y(int j){ return f[j-1]+a*tu(s[j-1])-b*s[j-1]; }
inline long double D(int j1, int j2)
	{ return (long double)(y(j2)-y(j1))/(x(j2)-x(j1)); }
int main() {
	freopen("special.in","r",stdin);
	freopen("special.out","w",stdout);
	scanf("%d %lld %lld %lld", &N, &a, &b, &c);
	for(int i=1; i<=N; ++i) 
		scanf("%lld", s+i), s[i] += s[i-1];
#define Hd q[hd]
	for(int i=1; i<=N; ++i) {
		while(hd+1<tl && D(q[tl-2], q[tl-1]) < D(q[tl-1], i)) --tl; 
		q[tl++] = i;
		while(hd+1<tl && D(q[hd], q[hd+1]) > h(i)) ++hd;
		f[i] = f[Hd-1]+a*tu(s[i]-s[Hd-1])+b*(s[i]-s[Hd-1])+c;
	}
	printf("%lld\n", f[N]);
	getchar(), getchar();
	return 0;
}