P16904 [CCO 2026] Asymmetry

Alice 和 Bob 将在一个有 $N$ 行 $M$ 列的网格上玩一个游戏，其中 $M$ 是偶数。还有一个正整数 $K$。初始时，网格的每个单元格包含一个介于 $0$ 和 $K$ 之间（含两端）的值，且每个单元格都是 **未标记** 的。玩家轮流操作，**Alice 先手**。当当前玩家无法进行操作时，游戏结束。 在每位玩家的回合中，他们选择一个网格中的 **未标记** 单元格，以及一个介于 $0$ 和 $K$ 之间（含两端）的整数 $a$。然后，将该单元格的值设置为 $a$，并将与所选单元格同一列的所有单元格 **标记**（包括所选单元格本身）。 网格的 **不对称度** 定义为：将网格沿垂直中线进行 **水平** 翻转后，每一对对应单元格的值之差的绝对值之和。更形式化地，它是 $$\sum_{1 \le i \le N} \left( \sum_{1 \le j \le M/2} |g_{i,j} - g_{i,M-j+1}| \right),$$ 其中 $g_{i,j}$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的单元格中的值。例如，下面的 $2 \times 4$ 网格的不对称度为 $|8-0|+|4-2|+|6-6|+|7-9|=12$。 $$ \begin{array}{|c|c|c|c|} \hline 8 & 4 & 2 & 0 \\ \hline 6 & 7 & 9 & 6 \\ \hline \end{array} $$ Alice 想要在游戏结束时最小化网格的不对称度，而 Bob 想要最大化它。如果双方都采取最优策略，最终网格的不对称度是多少？

输入的第一行包含 $3$ 个空格分隔的整数 $N$、$M$ 和 $K$（$1 \le N,M \le 2\,000$，$M$ 是偶数，$1 \le K \le 10^9$）。 接下来的 $N$ 行每行包含 $M$ 个整数，其中第 $i$ 行包含整数 $g_{i,1},\ldots,g_{i,M}$（$0 \le g_{i,j} \le K$），即从上往下第 $i$ 行从左到右的单元格的值。

输出一个整数，表示 Alice 和 Bob 都采取最优策略时最终网格的不对称度。

**样例输入 #1 的输出解释** 只有 $2$ 列，因此每位玩家将进行 $1$ 次操作。由于 Alice 先手，她可以执行以下操作： - 选择第一列中某个值为 $1$ 的单元格，将其值设为 $0$。那么 Bob 的最优操作是将同一行第二列的单元格的值设为 $1$。最终网格将与原网格类似，只是前两行中某行的 $0$ 和 $1$ 交换了位置。这样的网格不对称度为 $|1-0|+|0-1|+|0-0|=2$。 - 选择第二列前两行中的某个单元格，将其值设为 $1$。那么 Bob 的最优操作是将同一行第一列的单元格的值设为 $0$。同样，最终网格的不对称度为 $2$。 - 选择第三行中的一个单元格，将其值设为 $1$。那么 Bob 的最优操作可以是将第三行中另一个单元格的值设为 $0$。注意所选单元格原本的值就是 $0$，并且这样的操作是允许的。那么最终网格每一行都有一个 $0$ 和一个 $1$，导致不对称度为 $3$。 - 选择任意一个单元格，将其值设为其当前值。那么 Bob 的最优操作是将剩余的未标记列中第三行的单元格的值设为 $1$。最终网格每一行都有一个 $0$ 和一个 $1$，不对称度为 $3$。 我们可以看到，无论 Alice 如何操作，Bob 都能使不对称度至少为 $2$。如果 Alice 采用最优的第一步，她可以确保 Bob 无法使最终的不对称度超过 $2$。因此，双方均采取最优策略时的不对称度为 $2$。 **样例输入 #2 的输出解释** 只有一行，因此在每次操作中，当前玩家将选择一个未标记的单元格，并将其设为 $0$ 到 $21$ 之间（含两端）的任意值。双方各进行 $5$ 次操作后游戏结束，所有 $10$ 个单元格都被标记。 **样例输入 #3 的输出解释** 注意答案可能超出 $32$ 位整数的范围。 以下表格展示了可获得的 $25$ 分的分配情况： | 分值 | $N$ 的范围 | $M$ 的范围 | $K$ 的范围 | |:-:|:-:|:-:|:-:| | $2$ 分 | $N=1$ | $2 \le M \le 2\,000$ | $1 \le K \le 10^9$ | | $3$ 分 | $1 \le N \le 2\,000$ | $M=2$ | $K=1$ | | $3$ 分 | ^ | ^ | $1 \le K \le 10$ | | $3$ 分 | ^ | ^ | $1 \le K \le 10^9$ | | $4$ 分 | ^ | $2 \le M \le 2\,000$ | $K=1$ | | $4$ 分 | ^ | ^ | $1 \le K \le 10$ | | $6$ 分 | ^ | ^ | $1 \le K \le 10^9$ | 翻译由 DeepSeek V4 Pro 完成