思路：二维前缀和+二分

这个问题其实就是在求一个靠近 $\frac{sum}{2}$ 的最近的数，不过这个数是由正方形中的数的和组成的。

那么可以考虑枚举正方形的左上角端点，然后二分正方形的边长，找到一个正方形数之和大于等于 $\frac{sum}{2}$ 的最小边长。

而这里判断时需要快速求出一个正方形内数的和，可以通过预处理二维前缀和，然后查询可以$O(1)$计算出。

时间复杂度：$O(nmlogn)$

题目内容

在一个 $n \times m$ 的整数矩阵中，你需要挑选一个行数和列数相等的子矩阵（即正方形子矩阵）。记该子矩阵内所有元素之和为 $S_{\text{in}}$，矩阵其余部分所有元素之和为 $S_{\text{out}}$。你的目标是让 $|S_{\text{in}} - S_{\text{out}}|$ 尽可能小。请你计算这个最小可能值。

数据范围：矩阵的行数和列数均不超过 1000，矩阵中的每个数值均为不超过 10000 的正整数。

输入描述

第一行包含两个正整数 $n$ 和 $m$（$1 \le n, m \le 1000$），分别表示矩阵的行数和列数。 接下来 $n$ 行，每行包含 $m$ 个整数（数值范围 $1$ 到 $10000$），表示矩阵对应位置的元素。

输出描述

输出一个整数，表示能达到的最小差值 $|S_{\text{in}} - S_{\text{out}}|$。

样例1

输入

1 1
5

输出

5

说明

矩阵仅包含一个元素 5，因此只能选择边长 1 的正方形子矩阵。此时子矩阵和 $S_{\text{in}} = 5$，矩阵其余部分和 $S_{\text{out}} = 0$，差值 $|S_{\text{in}} - S_{\text{out}}| = |5 - 0| = 5$。这也是题目边界情况的最小可能值。

样例2

输入

3 3
1 1 1
1 1 1
1 1 1

输出

1

说明

矩阵所有元素均为 1，总和为 9。记正方形子矩阵的边长为 $k$，则子矩阵和 $S_{\text{in}} = k^2$，其余部分和 $S_{\text{out}} = 9 - k^2$。

• 当 $k = 1$ 时，差值为 $|1 - 8| = 7$；
• 当 $k = 2$ 时，差值为 $|4 - 5| = 1$；
• 当 $k = 3$ 时，差值为 $|9 - 0| = 9$。

因此最小差值出现在 $k = 2$ 时，结果为 1。

样例3

输入

2 3
1 2 3
4 5 6

输出

3

说明

矩阵总和为 21。可能的正方形子矩阵边长最大为 $\min(2,3)=2$。

考虑所有边长 2 的正方形子矩阵：

• 选取左上角 $(0,0)$ 到右下角 $(1,1)$ 的子矩阵，包含元素 1,2,4,5，和 $S_{\text{in}} = 12$，$S_{\text{out}} = 9$，差值 $|12 - 9| = 3$；
• 选取左上角 $(0,1)$ 到右下角 $(1,2)$ 的子矩阵，包含元素 2,3,5,6，和 $S_{\text{in}} = 16$，$S_{\text{out}} = 5$，差值 $|16 - 5| = 11$。

边长 1 的子矩阵和均不超过 6，与另一半的差值均大于 3。因此最小差值为 3。

样例4

输入

4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

输出

10

说明

矩阵元素为 $1$ 到 $16$ 的递增序列，总和 $= 136$。

考虑边长为 3 的正方形子矩阵，共有四个可能位置：

• 左上角 $(0,0)$：和 $= 1+2+3+5+6+7+9+10+11 = 54$，差值 $|54 - 82| = 28$；
• 左上角 $(0,1)$：和 $= 2+3+4+6+7+8+10+11+12 = 63$，差值 $|63 - 73| = 10$；
• 左上角 $(1,0)$：和 $= 5+6+7+9+10+11+13+14+15 = 90$，差值 $|90 - 46| = 44$；
• 左上角 $(1,1)$：和 $= 6+7+8+10+11+12+14+15+16 = 99$，差值 $|99 - 37| = 62$。

边长为 2 的子矩阵和最大为 $54$，差值均大于 $10$；边长为 4 的整个矩阵差值为 $136$。因此最小差值为 10。