题目分析

设初始矩形大小为 $(n_r, m_r)$，当前矩形为 $(n, m)$。删一行即 $n$ 减一，删一列即 $m$ 减一。当 $n=0$ 或 $m=0$ 时土地耕完。不难发现 $n$ 和 $m$ 不会同时减到 $0$，假设土地耕完时 $n=0$。

答案 $ans = \min \{ n_r + m_r - n - m \} = \min \{m_r - m\} + n_r = m_r + n_r - m_{max}$，问题转化为最大化 $m$。一个贪心的想法，能删行尽量删行，不能删行时才删列。但不好确定删上面的列还是下面的列。

考虑 DP，设 $f (i, j) = (x, y)$ 表示删到列区间为 $[i, j]$ 能删到的最小行区间 $[x, y]$。那么满足 $[x, y] = \varnothing$ 的 $j - i + 1$ 即为候选的 $m_{max}$。

几个结论：

对于每个合法的 $[i, j]$，$f(i, j)$ 取值唯一。

证明：

反证法，假设存在 $[x, y], [a, b]$ 皆为删到列区间 $[i, j]$ 时能删到的最小行区间，发现能构造一个严格更小的行区间 $[x, y] \cap [a, b]$，与 $[x, y], [a, b]$ 最小的前提矛盾，假设不成立，原命题成立。

对于合法的 $[i, j], [x, y]$，若 $[x, y] \subseteq [i, j]$，则有 $f (x, y) \subseteq f (i, j)$。

证明：

反证法，假设存在一行 $a$，满足 $a \in f (x, y)$ 且 $a \not \in f (i, j)$。
记 $c (x, y, z)$ 为第 $z$ 行 $[x, y]$ 区间的难度和，那么有 $c (i, j, a) \leq k < c (x, y, a)$，又有 $c (i, j, a) \geq c (x, y, a)$，与不等式矛盾，故假设不成立，原命题成立。

有了上面的结论就很好 DP 了。转移有 $f(i, j) \to f (i + 1, j)$ 和 $f (i, j) \to f (i, j - 1)$，继承转移来的区间后暴力求出最小区间。由结论 2. 保证复杂度正确，为 $O(n^2)$。

另外，对行考虑完后再对列做一遍。