### Brief description:

略。）

### Analysis:

記代價函數 $$!w(x) = ax^2 + bx + c$$

然後：

$$! \begin{aligned} f_i &= \min_{0 \leq j < i}\big\{ f_j + w(s_i-s_j)\big\} \\ &= \min_{0 \leq j < i}\big\{ f_j + as_j^2 - bs_j -2as_is_j\big\} + w(s_i) \end{aligned}$$ 寫成斜率優化的標準形式，b = kx + y 這裡有：

- $$k = -2as_i$$
- $$x = s_j $$
- $$y = f_j + as_j^2 – bs_j $$

這裡 $$x$$ 和 $$k$$ 均單調（因為 $$s_i$$ 單調），單調隊列即可。

//}/* .................................................................................................................................. */ const int N = int(1e6) + 9; LL f[N], s[N], a, b, c; int q[N], cz, op; int n; LL det(LL x1, LL y1, LL x2, LL y2){ return x1*y2 - x2*y1; } #define k (-2*a*s[i]) #define x(j) (s[j]) #define y(j) (f[j]+a*sqr(x(j)) - b*(x(j))) #define eval(j) (k*x(j)+y(j)) int dett(int p0, int p1, int p2){ LL t = det(x(p1)-x(p0), y(p1)-y(p0), x(p2)-x(p0), y(p2)-y(p0)); return t < 0 ? -1 : t > 0; } LL w(LL x){ return a*x*x+b*x+c; } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif RD(n); RDD(a, b, c); REP_1(i, n) s[i] = s[i-1] + RD(); cz = 0, op = 0; REP_1(i, n){ while (cz < op && eval(q[cz]) <= eval(q[cz+1])) ++cz; f[i] = eval(q[cz]) + w(s[i]); while (cz < op && dett(q[op-1], q[op], i) >= 0) --op; q[++op] = i; } OT(f[n]); }