好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

原题来自：APIO 2010

你有一支由 $n$ 名预备役士兵组成的部队，士兵分别编号为 $1 \dots n$，要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如 $(i,i+1,\dots,i+k)$ 的序列。编号为 $i$ 的士兵的初始战斗力为 $x_i$，一支特别行动队的初始战斗力 $x$ 为队内士兵初始战斗力之和，即 $x = x_i + x_{i+1} + \dots + x_{i+k}$。

通过长期的观察，你总结出一支特别行动队的初始战斗力 $x$ 将按如下经验公式修正为 $x'$：

$$x' = a x^2 + b x + c$$

其中 $a,b,c$ 是已知的系数（$a<0$）。作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队修正后战斗力之和最大。试求出这个最大和。

例如，你有 $4$ 名士兵，$x_1=2,x_2=2,x_3=3,x_4=4$。经验公式中的参数为 $a=-1,b=10,c=-20$。此时，最佳方案是将士兵组成 $3$ 个特别行动队：第一队包含士兵 $1$ 和士兵 $2$，第二队包含士兵 $3$，第三队包含士兵 $4$。特别行动队的初始战斗力分别为 $4,3,4$，修正后的战斗力分别为 $4,1,4$。修正后的战斗力和为 $9$，没有其它方案能使修正后的战斗力和更大。

---

输入格式

输入由三行组成：

• 第一行包含一个整数 $n$，表示士兵的总数；
• 第二行包含三个整数 $a,b,c$，经验公式中各项的系数；
• 第三行包含 $n$ 个用空格分隔的整数 $x_1,x_2,\dots,x_n$，分别表示编号为 $1,2,\dots,n$ 的士兵的初始战斗力。

---

输出格式

输出一个整数，表示所有特别行动队修正后战斗力之和的最大值。

---

样例

样例输入

4
-1 10 -20
2 2 3 4

样例输出

9

样例说明

$n=4, a=-1, b=10, c=-20$，士兵战斗力 $[2,2,3,4]$。

最优分组：$(1,2), (3), (4)$：

• 第一队：$x=2+2=4$，$x' = (-1)\times 4^2 + 10\times 4 + (-20) = -16+40-20=4$；
• 第二队：$x=3$，$x' = (-1)\times 9 + 30 -20 = -9+30-20=1$；
• 第三队：$x=4$，$x' = (-1)\times 16 + 40 -20 = -16+40-20=4$； 总和 $4+1+4=9$。

---

数据范围

• 对于 $20\%$ 的数据，$n \le 1000$；
• 对于 $50\%$ 的数据，$n \le 10^4$；
• 对于 $100\%$ 的数据：
  • $1 \le n \le 10^6$
  • $-5 \le a \le -1$
  • $|b|, |c| \le 10^7$
  • $1 \le x_i \le 100$

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

---

提示
此题为 斜率优化 DP 问题。

状态设计：
设 $dp[i]$ 表示前 $i$ 个士兵分成若干特别行动队，修正后战斗力之和的最大值。

转移方程：
考虑最后一段行动队为 $(j+1, j+2, \dots, i)$，其初始战斗力为 $S_i - S_j$，其中 $S_i$ 是 $x_i$ 的前缀和。

则：

$$dp[i] = \max_{0 \le j < i} \left\{ dp[j] + a(S_i - S_j)^2 + b(S_i - S_j) + c \right\}$$

展开：

$$dp[i] = \max_{0 \le j < i} \left\{ dp[j] + aS_i^2 - 2aS_i S_j + aS_j^2 + bS_i - bS_j + c \right\}$$

合并与 $j$ 无关的项：

$$dp[i] = aS_i^2 + bS_i + c + \max_{0 \le j < i} \left\{ dp[j] - 2aS_i S_j + aS_j^2 - bS_j \right\}$$

令 $A_j = S_j$, $B_j = dp[j] + aS_j^2 - bS_j$，则：

$$dp[i] = aS_i^2 + bS_i + c + \max_{0 \le j < i} \left\{ B_j - 2aS_i A_j \right\}$$

注意 $a<0$，所以 $-2a > 0$，令 $k_i = -2a S_i$（$k_i>0$），则：

$$dp[i] = aS_i^2 + bS_i + c + \max_{0 \le j < i} \left\{ B_j + k_i A_j \right\}$$

这是斜率优化形式：$\max\{ B_j + k_i A_j \}$。

斜率优化：
对于 $j_1 < j_2$，决策 $j_2$ 优于 $j_1$ 的条件为：

$$\frac{B_{j_2} - B_{j_1}}{A_{j_2} - A_{j_1}} \ge -k_i$$

但 $k_i$ 随 $i$ 变化，且 $S_i$ 单调递增（$x_i>0$），$k_i$ 单调递增（因为 $a<0$，$-2a>0$，$S_i$ 递增）。$A_j = S_j$ 也单调递增。

我们需要维护上凸包（因为求最大值），用单调队列维护。

步骤：

1. 计算前缀和 $S_i$；
2. 初始化队列，将 $j=0$ 入队（$A_0=0, B_0=0$）；
3. 遍历 $i$ 从 $1$ 到 $n$：
   • 若队首两点斜率 $\ge -k_i$，则弹出队首；
   • 取队首 $j$ 计算 $dp[i]$；
   • 将 $(A_i, B_i)$ 加入队尾，维护上凸包（弹出队尾下凸点）；
4. 输出 $dp[n]$。

复杂度 $O(n)$。

注意：

• $a<0$，所以 $-2a>0$，$k_i$ 为正且单调递增；
• 由于求最大值，维护上凸包；
• 斜率比较时注意用乘法避免浮点数误差。