AT_joig2021_f デジタルアート (Digital Art)

JOI 高中的学生葵喜欢制作数字艺术作品，今天她又创作了一幅新图片。 这幅图片的尺寸是 $ H $ 行 $ W $ 列，可以用一个 $ H \times W $ 的网格来表示。行号从上到下为 $ i $（$ 1 \leq i \leq H $），列号从左到右为 $ j $（$ 1 \leq j \leq W $）。每个像素都有一种颜色，颜色编号为从 1 到 256 之间的一个整数，像素 $ (i, j) $ 的颜色编号为 $ A_{i, j} $。 葵将这幅作品展示给她的同学凛，但凛认为图片中使用的颜色种类过多，因此不太喜欢。为了让凛满意，葵决定隐藏图片中的某些区域，以尽可能减少可见的颜色种类。 - 葵可以选择最多 $ S $ 个像素进行隐藏。 - 需要注意的是，隐藏的像素必须构成一个矩形区域。 给定图片的数据和隐藏像素的数量上限 $ S $，编写一个程序，计算在隐藏某个区域后，最少能看到多少种颜色。

输入通过标准输入提供，格式如下： > $ H\ W\ S\ A_{1,1}\ A_{1,2}\ \cdots\ A_{1,W}\ A_{2,1}\ A_{2,2}\ \cdots\ A_{2,W}\ \ldots\ A_{H,1}\ A_{H,2}\ \cdots\ A_{H,W} $

输出在一个区域被隐藏后，可能可见的最少颜色种类数。如果可以隐藏所有像素，从而没有可见像素，则输出 `0`。

### 约束条件 - $ 1 \leq H \leq 1,000 $。 - $ 1 \leq W \leq 1,000 $。 - $ 1 \leq S \leq HW $。 - $ 1 \leq A_{i, j} \leq 256 $ （$ 1 \leq i \leq H $，$ 1 \leq j \leq W $）。 - 所有输入值均为整数。 ### 子任务 1. （8 分）$ H = 1 $，$ W \leq 10 $。 2. （10 分）$ H \leq 10 $，$ W \leq 10 $。 3. （5 分）$ S = 1 $。 4. （6 分）所有颜色编号 $ A_{i, j} \leq 2 $。 5. （5 分）所有颜色编号 $ A_{i, j} \leq 4 $。 6. （13 分）所有颜色编号 $ A_{i, j} \leq 15 $。 7. （13 分）所有颜色编号 $ A_{i, j} \leq 30 $。 8. （15 分）所有颜色编号 $ A_{i, j} \leq 70 $。 9. （25 分）无其他限制。 ### 评分标准 所有提交将在评测系统中评分。 只有当程序为每个子任务的所有测试数据返回正确结果时，该子任务才被认为是正确的。 提交程序的得分是根据其成功解答的所有子任务的分数总和计算的。 最终得分是所有提交中的最高得分。 你可以在“提交结果”标签页中查看当前得分。 ### 样例解释 1 例如，隐藏第 2 列到第 8 列的像素后，仅能看到颜色编号为 5 和 6 的像素，颜色种类数为 2。这时，隐藏了 7 个像素，满足条件。葵无法使可见颜色种类少于 2，因此输出 2。此输入满足子任务 1、2、6、7、8 和 9 的限制。 ### 样例解释 2 例如，隐藏以像素 $ (2, 1) $ 为左上角和 $ (7, 7) $ 为右下角的矩形区域后，仅能看到颜色编号 1、3、4 和 5，颜色种类数为 4。这时，隐藏了 42 个像素，满足条件。如下图所示： 此输入满足子任务 2、6、7、8 和 9 的限制。 ### 样例解释 3 在最多只能隐藏 $ S = 1 $ 个像素的情况下，葵无法减少可见颜色种类，仍能看到 1 到 9 的 9 种颜色。因此输出 9。此输入满足子任务 2、3、6、7、8 和 9 的限制。 ### 样例解释 4 可以隐藏所有 54 个像素，使没有可见像素，因此输出 0。此输入满足子任务 2、6、7、8 和 9 的限制。 ### 样例解释 5 例如，隐藏以像素 $ (3, 1) $ 为左上角和 $ (10, 7) $ 为右下角的矩形区域后，仅能看到颜色编号为 1 和 3，颜色种类数为 2。这时，隐藏了 56 个像素，满足条件。如下图所示： 此输入满足子任务 2、5、6、7、8 和 9 的限制。 **本翻译由 AI 自动生成**