P13345 [EGOI 2025] IMO

滥用本题评测资源将被封号。

国际数学奥林匹克（IMO）是一项面向高中生的数学竞赛，每年举办一次。2025 年的 IMO 正好与 EGOI 同时进行。当你读到这道题时，两天的 IMO 正赛已经结束，评分工作也大概接近尾声。与 EGOI 这样的程序设计竞赛不同，IMO 的评分完全依靠人工完成，这是一项漫长而繁琐的工作。 今年的 IMO 包含 $M$ 道题目（编号为 $0$ 到 $M-1$），每道题的满分为 $K$ 分。有 $N$ 名选手参加比赛。第 $i$ 名选手在第 $j$ 道题上的得分为 $a_{i,j}$，其中 $a_{i,j}$ 是 $0$ 到 $K$ 之间的整数（包含 $0$ 和 $K$）。选手的排名由总分决定，若总分相同，则按选手编号（索引）从小到大排名。更正式地说，若满足以下条件之一，则选手 $x$ 的排名高于选手 $y$： * 选手 $x$ 的总分大于选手 $y$ 的总分， * 或者两人总分相同且 $x < y$。 为了公布最终排名，主办方需要公开部分 $a_{i,j}$ 的值。若某个值未公开，则只知道它是 $0$ 到 $K$ 之间的某个整数。 主办方希望尽量少地公开 $a_{i,j}$ 的值。同时，他们必须确保所有人都能唯一确定最终排名。换言之，主办方需要公开一组 $a_{i,j}$，使得与这些信息相符的排名只有唯一的正确排名。 请你求出最小的 $S$，使得最多只需公开 $S$ 个 $a_{i,j}$，就能唯一确定所有选手的完整排名。

第一行包含三个整数 $N$、$M$ 和 $K$，分别表示选手数、题目数和每题的最高分。 接下来 $N$ 行，每行 $M$ 个整数，第 $i$ 行为 $a_{i,0}, a_{i,1}, \ldots, a_{i,M-1}$。

输出一个整数 $S$，表示唯一确定最终排名所需公开的最少分数个数。

### 样例说明 在第一个样例中，只需公开 20 个分数即可，方案如下： | 7 | 7 | 0 | $\cdot$ | 7 | $\cdot$ | | --- | --- | --- | --- | --- | --- | | 7 | 3 | 0 | 7 | 2 | 1 | | $\cdot$ | 0 | 0 | $\cdot$ | 0 | 0 | | 7 | 7 | 7 | 7 | 7 | 1 | 此时，第三名选手的总分已知在 $0$ 到 $14$ 之间，肯定低于其他所有人。可以证明，不能再少公开一个分数。例如，如果隐藏第三名选手的某个 $0$，那么他的总分最高可达 $21$，这就可能导致第二名选手的总分 $20$ 无法保证排在第三名前面。 第一个样例满足测试组 5 和 6 的约束。 在第二个样例中，只需公开第一名选手的唯一分数，或者只公开第二名选手的唯一分数（不可都公开）。如果只公开第一名选手的分数，就能确定他总分为 $1$，即使第二名选手分数也是 $1$，第一名选手编号更小，排名更高。类似地，如果只公开第二名选手的分数，可知他总分为 $0$，无论第一名得多少分，第一名都排名更高。 第二个样例满足测试组 2、3、4、5、6 的约束。 第三个样例满足测试组 2、3、5、6 的约束。 第四个样例满足所有测试组的约束。 ### 约束与评分 * $2 \leq N \leq 20000$ * $1 \leq M \leq 100$ * $1 \leq K \leq 100$ * $0 \leq a_{i,j} \leq K$，对所有 $0 \leq i \leq N-1$，$0 \leq j \leq M-1$ 你的解答将在一组测试组上进行评测，每组包含若干测试用例。要获得该测试组的分数，你需要通过该测试组的所有测试用例。 | 测试组 | 分值 | 限制条件 | | :-: | :-: | :-: | | 1 | 10 | $N = M = 2$ 且 $K = 1$ | | 2 | 13 | $N = 2$ | | 3 | 10 | $N \cdot M \leq 16$ | | 4 | 18 | $K = 1$ | | 5 | 21 | $N \leq 10000$ 且 $M, K \leq 10$ | | 6 | 28 | 无额外限制 | 翻译由 ChatGPT-4.1 完成。