思路与算法

令 $S_i$ 为前 $i$ 名士兵权值和，$F_i$ 为将这 $i$ 人全部分组后的最大收益，$F_0=0$。最后一组为 $j+1,\ldots,i$：

$$F_i=\max_{0\le j<i}\{F_j+a(S_i-S_j)^2+b(S_i-S_j)+c\}.$$

展开得到

$$F_i=aS_i^2+bS_i+c+\max_{j<i}\{(-2aS_j)S_i+F_j+aS_j^2-bS_j\}.$$

前驱 $j$ 对应斜率 $-2aS_j$、截距 $F_j+aS_j^2-bS_j$ 的直线，在 $S_i$ 处查询最大值。

因为 $x_i>0$，前缀严格递增；又因 $a<0$，插入斜率也严格递增。用单调队列维护最大值上凸包。先放入 $j=0$ 的零直线，逐个读权值并累加前缀，先查询得到 $F_i$，最后插入该状态。队首淘汰当前及以后不可能最优的线，队尾按交点次序淘汰冗余线，无需保存所有前缀或逐一枚举分割点。

正确性说明

任一完整划分有唯一末组起点，删除末组后前缀必须最优，否则替换能改善原方案；任一合法前缀加末组也合法。因此枚举 $j<i$ 的递推精确描述最优收益。

展开平方保持每个候选值不变，最大直线查询等价于所有前驱枚举。斜率递增时，若相邻三线交点顺序使中间线不再拥有优势区间，删去它不影响最大值；用128位交叉乘积精确判断。查询点递增，后线当前不差于队首时，由更大斜率可知以后也不差，故队首可永久删除。凸包保留一个最优前驱。处理 $i$ 前仅有状态 $0,\ldots,i-1$，组均非空，由基础状态归纳最终 $F_n$ 是全部士兵的最大收益。

复杂度

队列按 $n+1$ 元素初始化，时间和空间均为 $O(n)$。每个前驱只入队一次，至多从队首或队尾删除一次，输入、前缀更新和查询摊还 $O(n)$。包含初始化的总时间 $O(n)$，额外空间 $O(n)$，输入缓冲为固定大小。

易错点

1. 必须覆盖全部士兵，答案可能为负，不得把各 $F_i$ 与零取最大。只有空前缀为零。
2. 本题是斜率递增的最大值上凸包，不可照抄最小值的弹出方向。
3. 先查询后插入确保末组非空。负 $a$ 和正权值是单调性的必要前提。
4. 前缀至 $10^8$，二次项、截距和直线值用 long long，交叉乘积先提升至 __int128，避免浮点交点误差。
5. $b,c$ 可负，快速输入保留负号。覆盖单人负答案、百万最大权值、全1、大正负常数。测试为非官方训练数据。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Input {
    static const int S = 1 << 16;
    char data[S];
    int at = 0, length = 0;
    int get() {
        if (at == length) {
            length = fread(data, 1, S, stdin);
            at = 0;
            if (!length)
                return EOF;
        }
        return data[at++];
    }
    ll next() {
        int ch = get();
        while (ch <= 32 && ch != EOF)
            ch = get();
        bool negative = ch == '-';
        if (negative)
            ch = get();
        ll value = 0;
        while (ch >= '0' && ch <= '9') {
            value = value * 10 + ch - '0';
            ch = get();
        }
        return negative ? -value : value;
    }
};
struct Line {
    ll m, b;
    ll value(ll x) const {
        return m * x + b;
    }
};
bool obsolete(Line a, Line b, Line c) {
    return (__int128)(a.b - b.b) * (c.m - b.m) >= (__int128)(b.b - c.b) * (b.m - a.m);
}
int main() {
    Input in;
    int n = in.next();
    ll a = in.next(), b = in.next(), c = in.next();
    vector<Line> q(n + 1);
    int head = 0, tail = 1;
    q[0] = {0, 0};
    ll prefix = 0, result = 0;
    for (int i = 1; i <= n; ++i) {
        prefix += in.next();
        while (tail - head >= 2 && q[head].value(prefix) <= q[head + 1].value(prefix))
            ++head;
        result = a * prefix * prefix + b * prefix + c + q[head].value(prefix);
        Line line = {-2 * a * prefix, result + a * prefix * prefix - b * prefix};
        while (tail - head >= 2 && obsolete(q[tail - 2], q[tail - 1], line))
            --tail;
        q[tail++] = line;
    }
    printf("%lld\n", result);
}