← 返回题目列表

AtCoder · joig2021_f

F. 数字艺术

中文机器翻译题面 查看原题

配点: 100 点

問題文

JOI高中生葵有创作数字艺术的爱好,今天她创造了一个新形象。

该图像的大小为 H 像素,水平 W 像素, 它以H \times W 网格的形式表示。在这里,从上面 i 行目 (1 \leqq i \leqq H),从左起 j 列目 (1 \leqq j \leqq W) 像素 由 (i, j) 代表。每个像素是 1 它有两种颜色。每种颜色都有 像素编号最大为 1 减去 256 。 (i, j) 的颜色编号是 A_{i, j} 。

Aoi 向她的同学 Rin 展示了这张图像,但 Rin 不喜欢它,因为“图像中使用了太多不同的颜色。”因此,Aoi 想知道是否可以隐藏图像中的某些区域,如下所示,以尽量减少可见颜色的数量。

  • 葵是 选择并隐藏最多 S 像素。
  • 然而,隐藏像素的面积是 1 必须由两个矩形表示。

图像数据和隐藏像素数上限 给定 S ,编写一个程序,找出当图像中的某个区域被隐藏时可以看到的最小可能颜色数。

制約

  • 1 \leqq H \leqq 1\,000.
  • 1 \leqq W \leqq 1\,000.
  • 1 \leqq S \leqq HW.
  • 1 \leqq A_{i, j} \leqq 256 (1 \leqq i \leqq H,1 \leqq j \leqq W).
  • 所有输入值都是整数。

小課題

  1. (8 点) H = 1,W \leqq 10.
  2. (10 点) H \leqq 10,W \leqq 10.
  3. (5 点) S = 1.
  4. (6 点) A_{i, j} \leqq 2 (1 \leqq i \leqq H,1 \leqq j \leqq W).
  5. (5 点) A_{i, j} \leqq 4 (1 \leqq i \leqq H,1 \leqq j \leqq W).
  6. (13 点) A_{i, j} \leqq 15 (1 \leqq i \leqq H,1 \leqq j \leqq W).
  7. (13 点) A_{i, j} \leqq 30 (1 \leqq i \leqq H,1 \leqq j \leqq W).
  8. (15 点) A_{i, j} \leqq 70 (1 \leqq i \leqq H,1 \leqq j \leqq W).
  9. (25 点)没有额外的限制。

评分注意事项

所有提交的内容都将通过评审系统进行评分。

当提交的源代码为与该子作业对应的所有评分输入数据返回正确的结果时,该源代码被认为对于该子作业是正确的。

每次提交的分数是所提交的源代码回答正确的子任务分数的总和。

该作业的分数是此作业所有提交的最高分。

您可以在“提交结果”选项卡上的“我的分数状态”中查看您当前的分数。


入力

输入是按以下格式从标准输入给出的。

H W S
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}

出力

将隐藏图像中的某个区域时可以看到的最小可能颜色数输出到标准输出。 1 行。

特别是如果您可以使任何像素都不可见 输出 0 。


入力例 1

1 10 7
5 1 2 5 2 2 5 6 6 5

出力例 1

2

例如,从左数 从第 2 起 如果隐藏像素达到 8 ,则数字 仅 5, 6 颜色可见,类型数量为 2 变为。在这种情况下,隐藏像素是 有 7 块满足条件。此外,葵还可以看到颜色。 1 不能小于类型。因此 2 。

此输入示例是一个小作业。 它满足 1, 2, 6, 7, 8, 9 满足约束。


入力例 2

10 10 45
1 1 1 1 1 1 1 1 1 1
1 1 1 2 2 3 3 1 1 1
1 1 2 1 2 3 1 3 1 1
1 2 1 2 6 6 3 1 3 1
1 2 2 6 1 1 6 3 3 1
1 4 4 6 1 1 6 5 5 1
1 4 1 4 6 6 5 1 5 1
1 1 4 1 4 5 1 5 1 1
1 1 1 4 4 5 5 1 1 1
1 1 1 1 1 1 1 1 1 1

出力例 2

4

例如,左上角的像素 (2, 1),右下像素 如果用 (7, 7) 隐藏矩形区域,则数字 有 1, 3, 4, 5 颜色可见,类型数量为 4 变为。在这种情况下,隐藏像素是 有 42 块满足条件。

这个解释可以用如下图来表达。

此输入示例是一个小作业。 它满足 2, 6, 7, 8, 9 满足约束。


入力例 3

5 10 1
2 3 5 7 1 1 1 3 1 7
1 9 2 3 2 9 3 1 3 7
4 1 4 3 4 7 5 3 5 9
6 1 6 7 7 1 7 3 7 9
8 3 8 9 9 7 2 3 5 7

出力例 3

9

隐藏像素 在数量小于或等于 S = 1 的条件下,葵可以 1, 2, 3, \ldots, 9 的 9 您只能使不同的颜色可见。因此 您可以隐藏所有 9 。

此输入示例是一个小作业。 它满足 2, 3, 6, 7, 8, 9 满足约束。


入力例 4

9 6 54
1 1 1 1 1 3
6 14 14 3 3 12
9 13 1 10 3 3
9 13 5 5 3 3
6 13 10 3 7 3
2 5 8 5 3 3
6 5 5 3 15 3
6 5 10 5 3 3
2 2 5 7 3 3

出力例 4

0

54 像素,以便没有像素可见。因此 0 。

此输入示例是一个小作业。 它满足 2, 6, 7, 8, 9 满足约束。


入力例 5

8 10 59
3 3 3 3 3 3 3 3 2 3
3 1 3 3 3 3 3 2 3 3
3 3 1 4 3 4 2 3 3 3
3 3 3 1 4 2 4 3 3 3
3 3 3 4 1 4 2 3 3 3
3 3 3 1 4 3 4 2 3 3
3 3 1 3 3 3 3 3 2 3
3 1 3 3 3 3 3 3 3 3

出力例 5

2

例如,左上角的像素 (3, 1),右下像素 如果用 (10, 7) 隐藏矩形区域,则数字 有 1, 3 颜色可见,类型数量为 2 变为。在这种情况下,隐藏像素是 有 56 块满足条件。

这个解释可以用如下图来表达。

此输入示例是一个小作业。 它满足 2, 5, 6, 7, 8, 9 满足约束。