斜率优化
# include# include # include # include # include # define Sqr(x) (1LL * (x) * (x))# define IL inline# define RG register# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;IL ll Read(){ RG char c = getchar(); RG ll x = 0, z = 1; for(; c > '9' || c < '0'; c = getchar()) z = c == '-' ? -1 : 1;; for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0'; return x * z;}const int MAXN(1000010);int n, Q[MAXN], head, tail;ll f[MAXN], sum[MAXN], a, b, c;IL ll F(RG ll x){ return a * Sqr(x) + b * x + c;}IL double K(RG int i, RG int j){ RG ll x1 = 2 * a * sum[i], y1 = f[i] + a * Sqr(sum[i]) - b * sum[i]; RG ll x2 = 2 * a * sum[j], y2 = f[j] + a * Sqr(sum[j]) - b * sum[j]; return 1.0 * (y2 - y1) / (x2 - x1);}int main(){ n = Read(); a = Read(); b = Read(); c = Read(); for(RG int i = 1; i <= n; i++) sum[i] = sum[i - 1] + Read(); for(RG int i = 1; i <= n; i++){ while(head < tail && K(Q[head], Q[head + 1]) <= sum[i]) head++; f[i] = f[Q[head]] + F(sum[i] - sum[Q[head]]); while(head < tail && K(Q[tail - 1], Q[tail]) >= K(Q[tail], i)) tail--; Q[++tail] = i; } printf("%lld\n", f[n]); return 0;}