APIO 2014 Commando with CHT

commando.cpp

#include <bits/stdc++.h>
using namespace std;

struct line {
	long long a, b;
};
vector<line> S;
double cross(line L1, line L2) {
	if(L1.a == L2.a) return L1.b <= L2.b ? -1e18 : 1e18;
	return (double)(L1.b - L2.b) / (L2.a - L1.a);
}
void add(long long a, long long b) {
	line ln = {a, b};
	while(S.size() >= 2 && cross(S.back(), ln) < cross(S[S.size() - 2], S.back()))
		S.pop_back();
	S.push_back(ln);
}
long long query(long long x) {
	int lo = 0, hi = S.size() - 1;
	while(lo < hi) {
		int mid = (lo + hi) / 2;
		double p = cross(S[mid], S[mid+1]);
		if(p < x) lo = mid + 1;
		else hi = mid;
	}
	return S[lo].a*x + S[lo].b;
}

int n;
long long a, b, c, s[1000010], dp[1000010];
int main() {
	scanf("%d", &n);
	scanf("%lld%lld%lld", &a, &b, &c);
	add(b, 0);
	for(int i=1; i<=n; i++) {
		scanf("%lld", s+i);
		s[i] += s[i-1];
		dp[i] = query(s[i]) + 1ll*a*s[i]*s[i] + c;
		add(-2*a*s[i]+b, a*s[i]*s[i]-b*s[i]+dp[i]);
	}
	printf("%lld", dp[n]);
	return 0;
}