易得 $\mathcal O(n^2)$ 状态转移方程 $f_i\gets \max\limits_{j=0}^{j<i}\{f_j+a(s_i-s_j)^2+b(s_i-s_j)+c\}$，特殊的，约定 $f_0=0$。
考虑化简式子，
$$
\begin{aligned}
f_j+a(s_i-s_j)^2+b(s_i-s_j)+c
&= f_j+a(s_i^2-2\cdot s_i\cdot s_j+s_j^2)+b\cdot s_i-b\cdot s_j+c \\
&= f_j+a\cdot s_i^2-2a\cdot s_i\cdot s_j+a\cdot s_j^2+b\cdot s_i-b\cdot s_j+c\
\end{aligned}
$$
设函数 $F(i)$ 由上式只含有 $i$ 的项组成，$G(j)$ 由上式只含有 $j$ 的项组成。
那么
$$
\begin{aligned}
F(i)
&= a\cdot s_i^2+b\cdot s_i\\
G(i)
&= f_j+a\cdot s_j^2-b\cdot s_j
\end{aligned}
$$
则上式即为 $F(i)+G(j)+c$，那么转移方程即为 $f_i\gets \max\limits_{j=0}^{j<i}\{F(i)+G(j)-2a\cdot s_i\cdot s_j+c\}$。
发现 $F(i)+c$ 是共有的，那么便是 $f_i\gets \max\limits_{j=0}^{j<i}\{G(j)-2a\cdot s_i\cdot s_j\}+F(i)+c$。
约定 $j_1<j_2$，那么当 $j_1$ 转移优于 $j_2$ 即 $G(j_1)+2a\cdot s_i\cdot s_{j_1}>G(j_2)+2a\cdot s_i\cdot s_{j_2}$ 时，则有$(f_{j_1}+a\cdot s_{j_1}^2-b\cdot s_{j_1}-2a\cdot s_i\cdot s_{j_1})-(f_{j_2}+a\cdot s_{j_2}^2-b\cdot s_{j_2}-2a\cdot s_i\cdot s_{j_2})>0$。
移项得 $s_i>\dfrac{(f_{j_1}+a\cdot s_{j_1}^2-b\cdot s_{j_1})-(f_{j_2}+a\cdot s_{j_2}^2-b\cdot s_{j_2})}{2a(s_{j_1}-s_{j_2})}$。
题目说了 $a<0,x_i>0$，也就是 $s_{j_1}-s_{j_2}<0$，所以不用变号。
那么 $j_1$ 到 $j_2$ 的连线我们是可以看做是斜率 $k=\dfrac{(f_{j_1}+a\cdot s_{j_1}^2-b\cdot s_{j_1})-(f_{j_2}+a\cdot s_{j_2}^2-b\cdot s_{j_2})}{2a(s_{j_1}-s_{j_2})}$ 的直线。
然后使用单调队列维护凸壳就可以了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++
char buf[1000000], *p1 = buf, *p2 = buf;
template <typename T>
void read(T &x)
{
x = 0;
int f = 1;
char c = getchar();
for (; c < '0' || c > '9'; c = getchar())
if (c == '-')
f = -f;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
x *= f;
}
template <typename T, typename... Args>
void read(T &x, Args &...y)
{
read(x);
read(y...);
}
int n;
ll a, b, c;
ll s[1000020];
ll f[1000020];
int q[1000020];
ll hd, tl;
ll FF(int x) { return f[x] + a * (s[x] * s[x]) - b * s[x]; }
ld slope(int j1, int j2) { return (1.0 * FF(j1) - 1.0 * FF(j2)) / (2.0 * a * (s[j1] - s[j2])); }
int main()
{
read(n, a, b, c);
for (int i = 1; i <= n; i++)
read(s[i]), s[i] += s[i - 1];
q[hd = tl = 1] = 0;
for (int i = 1; i <= n; i++)
{
while (hd < tl && s[i] > slope(q[hd], q[hd + 1]))
hd++;
int j = q[hd];
f[i] = f[j] + a * (s[i] - s[j]) * (s[i] - s[j]) + b * (s[i] - s[j]) + c;
while (hd < tl && slope(q[tl - 1], q[tl]) > slope(q[tl], i))
tl--;
q[++tl] = i;
}
cout << f[n] << endl;
return 0;
}