← 返回题目列表

AtCoder · joig2023_e

E. 运河

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

配点: 100 点

問題文

JOIG王国是 H 行 W 它具有矩形形状,分为柱状网格。从上面 i 行目 (1 \leqq i \leqq H),从左起 j 列目 (1 \leqq j \leqq W) 它被称为 (i,j) 。

每个方格都有一个固定的整数,称为高程。鳟鱼 (i,j) 的海拔高度是 A_{i,j} 。

JOIG 王国决定修建一条横贯王国的运河。运河建设按如下方式进行。

  • 一些整数 k (1 \leqq k < W) 被确定。从左边开始 k 列和 k+1 在各行之间修建一条从王国顶部延伸至底部的运河。

这里我们指的是可以通过重复移动到彼此相邻且不穿过运河的相同标高的方格来相互移动的方格集合。 它被称为平地。为了便于管理国土,我们希望在确定运河建设地点时,尽量减少平坦面积。

给定 JOIG 王国的地形信息,编写一个程序,求运河建成后 JOIG 王国中可能出现的最少平坦区域的数量。

制約

  • H \geqq 1.
  • W \geqq 2.
  • H \times W \leqq 500\,000.
  • 1 \leqq A_{i,j} \leqq 10^9 (1 \leqq i \leqq H,1 \leqq j \leqq W).
  • 所有输入值均为整数。

小課題

  1. (6 点) H = 1.
  2. (20 点) H \leqq 2.
  3. (27 点) H \leqq 200,W \leqq 200.
  4. (47 点)没有额外的限制。

入力

输入按以下格式给出。

H W
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}

出力

输出修建运河后JOIG王国内可能存在的最少平地数量。 如果一条运河被建造为


入力例 1

4 4
1 1 1 3
2 2 1 3
2 1 1 3
2 2 2 2

出力例 1

4

k=3 ,那么JOIG王国将是 它分为 4 平坦区域。

  • 质量 由 (1,1),(1,2),(1,3),(2,3),(3,2),(3,3) 组成的 plain
  • 质量 由 (2,1),(2,2),(3,1),(4,1),(4,2),(4,3) 组成的 plain
  • 质量 由 (1,4),(2,4),(3,4) 组成的 plain
  • 质量 由 (4,4) 组成的 plain

JOIG 王国内平地数量 它不能小于 3 ,所以4 。

此输入是一个小作业 如果一条运河被建造为 3, 4 满足约束。 如果设置为


入力例 2

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

出力例 2

8

k=1 ,JOIG王国将 它分为 8 平坦区域。 JOIG 王国内平地数量 7 ,所以8 。

此输入是一个小作业 如果一条运河被建造为 3, 4 满足约束。 如果设置为


入力例 3

1 6
1 1 2 2 3 3

出力例 3

3

此输入满足所有子任务约束。


入力例 4

2 10
1 1 1 1 1 3 3 3 3 4
1 2 1 3 3 3 1 1 3 3

出力例 4

6

此输入是一个小作业 如果一条运河被建造为 2, 3, 4 满足约束。 如果设置为