题意

你有一支由 $n$ 名预备役士兵组成的部队，士兵从 $1$ 到 $n$ 编号，你要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如 $i,i+1,\cdots ,i+k$的序列。所有的队员都应该属于且仅属于一支特别行动队。

编号为 $i$ 的士兵的初始战斗力为 $x_i$ ，一支特别行动队的初始战斗力 $X$ 为队内士兵初始战斗力之和，即 $X=x_i+x_{i+1}+\cdots +x_{i+k}$。

通过长期的观察，你总结出对于一支初始战斗力为 $X$ 的特别行动队，其修正战斗力 $X^{\prime }=a{X}^2+bX+c$，其中 $a,b,c$ 是已知的系数。 作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队的修正战斗力之和最大。试求出这个最大和。

$1\le n\le 10^6$，$-5\le a\le -1$，$-10^7\le b,c\le 10^7$，$1\le x_i\le 100$。

思路

先考虑朴素的 dp，令 $f_i$ 表示将前 $i$ 个人分队完毕的最大战斗力，设：
$$s_i=\sum _{j=1}^i{x}_i,z(x)=a{x}^2+bx+c$$

那么有：
f i = max ⁡ j ∈ [ 1 , i ) { f j + z ( s i − s j ) } f_i=\max_{j\in[1,i)}\left \{f_j+z(s_i-s_j)\right \} fi​=j∈[1,i)max​{fj​+z(si​−sj​)}

去到了 $\Theta (n^2)$ 级别。由上一篇题解的经验，考虑使用斜率优化掉找 $j$ 的 $\Theta (n)$：

设有决策点 $j1$ 和 $j2$ 且 $j2$ 优于 $j1$，那么：
$$f_{j1}+z(s_i-s_{j1})\le f_{j2}+z(s_i-s_{j2})$$

$$f_{j1}+a(s_i-s_{j1}{)}^2+b(s_i-s_{j1})\le f_{j2}+a(s_i-s_{j2}{)}^2+b(s_i-sj2)$$

$$f_{j1}+a{s}_i^2+a{s}_{j1}^2-2a{s}_i{s}_{j1}+b{s}_i-b{s}_{j1}\le f_{j2}+a{s}_i^2+a{s}_{j2}^2-2a{s}_i{s}_{j2}+b{s}_i-b{s}_{j2}$$

$$f_{j1}-f_{j2}-b{s}_{j1}+b{s}_{j2}+a{s}_{j1}^2-a{s}_{j2}^2\le 2a{s}_i{s}_{j1}-2a{s}_i{s}_{j2}$$

$$f_{j1}-f_{j2}-b(s_{j1}-s_{j2})+a(s_{j1}^2-s_{j2}^2)\le 2a{s}_i(s_{j1}-s_{j2})$$

因为 $s_{j1}<s_{j2}$，因而注意变号：
$$\frac{f_{j1}-f_{j2}-b(s_{j1}-s_{j2})+a(s_{j1}^2-s_{j2}^2)}{2a(s_{j1}-s_{j2})}\ge s_i$$

那就不妨拿个 $g_i=a{s}_i^2+b{s}_i$ 来代换了：
$$\frac{f_{j1}-f_{j2}+g_{j1}-g_{j2}}{2a(s_{j1}-s_{j2})}\ge s_i$$

斜率 $slope\ge s_i$，$s_i$ 单增，由下图，扔到符合条件区间的尾巴去。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
const ll N=1e6+9,inf=0x3f3f3f3f;
ll n,a,b,c,x[N];
ll s[N],g[N],f[N],q[N];
ll _2(ll x)
{return x*x;
}
ll z(ll x)
{return a*_2(x)+b*x+c;
}
dd slope(ll j1,ll j2)
{return (dd)(f[j1]-f[j2]+g[j1]-g[j2])/(dd)(2*a*(s[j1]-s[j2]));
}
int main()
{scanf("%lld%lld%lld%lld",&n,&a,&b,&c);for(int i=1;i<=n;i++){scanf("%lld",&x[i]);s[i]=s[i-1]+x[i];g[i]=a*_2(s[i])-b*s[i];}memset(f,-inf,sizeof(f));ll hh=0,tt=0;f[0]=0;for(int i=1;i<=n;i++){while(hh<tt&&slope(q[hh],q[hh+1])<=s[i])hh++;//slope>s[i]单增，扔队尾 f[i]=f[q[hh]]+z(s[i]-s[q[hh]]);while(hh<tt&&slope(q[tt],i)<slope(q[tt-1],q[tt]))tt--;q[++tt]=i;}printf("%lld",f[n]);return 0;
}