传送门

题意

给定大小 $n \times m$ 的矩阵 $a_{i,j}$，记 $\displaystyle sum_{i, j} = \sum_{k = 1}^j a_{i, k}$。

可以选择 $n$ 个数 $j_1, j_2, \cdots, j_n$ 满足 $0 \le j_k \le m$ 且 $\displaystyle \sum_{k = 1}^n j_k = V$。求 $\displaystyle \sum_{k = 1}^n sum_{k, j_k}$ 的最大值。

$n \times m \le 3 \times 10 ^ 5$，$V \le n \times m$。

对任意 $1 \le i \le n$ 有 $a_{i, 1} \le a_{i, 2} \le \cdots \le a_{i, m}$ 或 $a_{i, 1} \ge a_{i, 2} \ge \cdots \ge a_{i, m}$，即对任意 $1 \le i \le n$ 有 $a_{i, j} (1 \le j \le m)$ 单调不减或单调不增。

解析

首先，我们可以将不增的和不减的分开考虑。

设 $f_x$ 为只考虑不增的时，$\displaystyle\sum_{k = 1}^n j_k = x$ 时的最大值，$g_x$ 为只考虑不减的时，$\displaystyle\sum_{k = 1}^n j_k = x$ 时的最大值。

则答案 $\displaystyle ANS = \max_{0 \le x \le V} (f_x + g_{V - x})$。

先求 $f_x$，其中 $0 \le x \le n \times m$。

设令 $a_{i, j}(1 \le j \le m)$ 不增的 $i$ 有 $I$ 个，则 $x > I \times m$ 时有 $f_x = f_{I \times m}$。所以只需要求 $0 \le x \le I \times m$ 时的 $f_x$。

贪心。将所有这样的 $i$ 对应的 $I \times m$ 个 $a_{i, j}$ 放在一起排序，取最大的 $x$ 个，它们的和就是 $f_x$。

:::success[证明] 只需证明这样是合法的，即证：若取了某个 $a_{i, j}$，则一定也取了 $a_{i, 1}, a_{i, 2}, \cdots, a_{i, j - 1}$。

因为 $a_{i, 1} \ge a_{i, 2} \ge \cdots \ge a_{i, j - 1}$，而又是从大到小取的，所以一定也取了 $a_{i, 1}, a_{i, 2}, \cdots, a_{i, j - 1}$。证毕。 :::

再求 $g_x$，其中 $0 \le x \le n \times m$。

同理，设令 $a_{i, j}(1 \le j \le m)$ 不减的 $i$ 有 $J$ 个，则 $x > J \times m$ 时有 $g_x = g_{J \times m}$。所以只需要求 $0 \le x \le J \times m$ 时的 $g_x$。

对于这样的 $i$，注意到 $a_{i, j} \le a_{i, j + 1}$，所以 $sum_{i, j - 1} + sum_{i, j + 1} \ge 2sum_{i, j}$。

所以 $sum_{i, j}(0 \le j \le m)$ 为下凸函数！

而 $g_x(0 \le x \le J \times m)$ 为下凸函数的卷积，所以合理猜测当 $k_i(1 \le i \le n)$ 几乎都取到边界时 $g_x$ 最大。

猜测：$g_x$ 最大时，可以使 $k_i$ 中至多有一个数 $\in (0, m)$。

:::success[证明] 反证法。假设有至少两个 $i$ 满足 $k_i \in (0, m)$。则这两行都选了但没选完。

设其中一行最后一个选的数为 $a$，第一个没选的数为 $b$，另一行最后一个选的数为 $c$，第一个没选的数为 $d$。

则 $a \le b$，$c \le d$。

若 $b \le d$，则 $a \le b \le d$。将 $a$ 去掉并加入 $d$，则 $g_x$ 不减，矛盾。

若 $b > d$，则 $c \le d < b$。将 $c$ 去掉并加入 $b$，则 $g_x$ 增加，亦矛盾。

证毕。 :::

所以 $g_x$ 取到最大值时，只有至多一行选了但没选完，其余的要么全选了要么都没选。

于是可以通过带余除法确定选了但没选完的那一行选了几个，以及有多少行全选了。

设 $x = qm+r$，其中 $q$ 为非负整数，$r \in [0, m)$。

分以下两种情况：

• 若 $r = 0$，则一定是有 $q$ 行全选了，其余的都没选。于是取总和最大的 $q$ 行即可。

• 若 $r > 0$，则有 $q$ 行全选了，有一行只选了 $r$ 个，其余的行没选。

  首先贪心的选取总和最大的 $q$ 行为全选的，则取剩下的行中 $sum_{i, r}$ 最大的 $i$ 对应的行选 $r$ 个。

  可以发现这样贪心是不对的，于是再考虑选 $r$ 个的行在总和最大的 $q$ 行中的情况。此时需要选剩下的当中总和最大的 $q$ 行全选，即总和最大的 $q + 1$ 行除去选 $r$ 个的行。

  所以可以先选了总和最大的 $q + 1$ 行，再选其中的一行删掉后 $m - r$ 个。取其中后 $m - r$ 个的和最小的一行即可。

其中需要求总和最大的 $q$ 行的和，不在总和最大的 $q$ 行中的行的 $sum_{i, r}$ 的最大值，总和最大的 $q + 1$ 行中后 $m - r$ 个的和的最小值，如果先按照总和从大到小的顺序将这 $n$ 行排序，则依次为前缀和，后缀最大值，前缀最小值，可以预处理。

这样就可以求出 $g_x$ 了。最后再求 $ANS$ 即可。

时间复杂度 $O(nm\log nm)$。

:::success[代码]

#define N 300005
#define ll long long
int n, m, k; ll a[N];
struct node {
    vector<ll> sum;
    node () {}
    void init() {sum.resize(m + 1, 0);}
    friend bool operator < (node a, node b) {return a.sum[m] > b.sum[m];}
};
node nd[N];
ll sum[N];
ll pre[N], suc[N];
int f(int i, int j) {return (i - 1) * m + j;}
int cnt = 0;
priority_queue<ll> q;
ll ans[N], ans_[N];
int main() {
    n = read<int>(); m = read<int>(); k = read<int>();
    for (int i = 1; i <= n; i++) {
        bool flg = true;
        for (int j = 1; j <= m; j++) {
            a[j] = read<ll>();
            if (j > 1 && a[j] > a[j - 1]) flg = false;
        } if (flg) {
            for (int j = 1; j <= m; j++) q.push(a[j]);
        } else {
            nd[++cnt].init();
            for (int j = 1; j <= m; j++) nd[cnt].sum[j] = nd[cnt].sum[j - 1] + a[j];
        }
    } sort(nd + 1, nd + cnt + 1); ll sm = 0;
    for (int i = 1; i <= (n - cnt) * m; i++) {
        sm += q.top(); q.pop();
        ans[i] = sm;
    } for (int i = (n - cnt) * m + 1; i <= n * m; i++) ans[i] = ans[i - 1];
    for (int i = 1; i <= cnt; i++) sum[i] = sum[i - 1] + nd[i].sum[m];
    for (int i = 1; i <= cnt; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1) pre[f(i, j)] = nd[i].sum[j] - nd[i].sum[m];
            else pre[f(i, j)] = max_(pre[f(i - 1, j)], nd[i].sum[j] - nd[i].sum[m]);
        }
    } for (int i = cnt; i >= 1; i--) {
        for (int j = 1; j <= m; j++) {
            if (i == cnt) suc[f(i, j)] = nd[i].sum[j];
            else suc[f(i, j)] = max_(suc[f(i + 1, j)], nd[i].sum[j]);
        }
    } for (int i = 1; i <= cnt * m; i++) {
        if (i % m == 0) {
            ans_[i] = sum[i / m];
        } else {
            int x = i / m, r = i % m;
            ans_[i] = max_(sum[x] + suc[f(x + 1, r)], sum[x + 1] + pre[f(x + 1, r)]);
        }
    } for (int i = cnt * m + 1; i <= n * m; i++) ans_[i] = ans_[i - 1];
    ll ANS = 0;
    for (int i = 0; i <= k; i++) ANS = max_(ANS, ans[i] + ans_[k - i]);
    writeln(ANS); return fl();
}

:::

提交记录

THE END