#P14860. [OOI2026 资格赛]Moving搬家

    ID: 14076 传统题 3000ms 1024MiB 尝试: 3 已通过: 1 难度: 10 上传者: 标签>CF3100NOI/NOI+/CTS同向双指针交换论证二分答案二分图建模Hall 定理状压 DP线性 DP一维前缀和单调队列优化 DP前后缀最值

[OOI2026 资格赛]Moving搬家

题目描述

考虑一个由 nn 行 mm 列组成的城市。每一行与每一列的交点处都有一栋房子。

最初,位于第 ii 行第 jj 列的房子 (i,j)(i,j) 中住着 ai,ja_{i,j} 个人。第二年,每个人都从原来的房子搬到了某个其他房子,也可以留在原来的房子中。已知第二年房子 (i,j)(i,j) 中住着 bi,jb_{i,j} 个人。

你需要输出最小的整数 xx,使得存在一种搬家方案,让每个人从原房子到新房子的距离都不超过 xx。

两个格子 (x1,y1)(x_1,y_1) 和 (x2,y2)(x_2,y_2) 之间的距离定义为:

∣x1−x2∣+∣y1−y2∣.|x_1-x_2|+|y_1-y_2|.

输入格式

每个测试包含多组测试用例。第一行包含一个整数 tt(1≤t≤1001 \le t \le 100),表示测试用例数量。

接下来描述每个测试用例。

每个测试用例第一行包含两个整数 n,mn,m(1≤n≤31 \le n \le 3,1≤m≤1000001 \le m \le 100000),表示表格的行数和列数。

接下来 nn 行描述初始居民数量。第 ii 行包含 mm 个整数 ai,1,ai,2,…,ai,ma_{i,1},a_{i,2},\ldots,a_{i,m}(0≤ai,j≤1090 \le a_{i,j} \le 10^9)。

再接下来 nn 行描述搬家后的居民数量。第 ii 行包含 mm 个整数 bi,1,bi,2,…,bi,mb_{i,1},b_{i,2},\ldots,b_{i,m}(0≤bi,j≤1090 \le b_{i,j} \le 10^9)。

保证所有 ai,ja_{i,j} 的和等于所有 bi,jb_{i,j} 的和。

令 MM 表示所有测试用例中 mm 的总和,保证 M≤100000M \le 100000。

输出格式

对每个测试用例,输出一个整数,表示最小的 xx,使得存在一种搬家方案,让每个人的移动距离都不超过 xx。

样例

样例输入

1
2 5
0 4 0 4 0
0 0 0 0 0
1 1 1 1 1
0 1 1 1 0

样例输出

2

样例解释

在样例中,来自房子 (1,2)(1,2) 的人分别搬到 (1,1)(1,1)、(1,2)(1,2)、(1,3)(1,3)、(2,2)(2,2);来自房子 (1,4)(1,4) 的人分别搬到 (1,4)(1,4)、(1,5)(1,5)、(2,3)(2,3)、(2,4)(2,4)。最大距离为 22。

计分方式

测试数据包含十二个测试组。只有当某组所有测试点以及该组要求的若干前置组均通过时,才能获得该组分数。注意,某些测试组不一定要求通过样例测试。离线测试表示该组测试结果会在比赛结束后才可见。

令 SS 为城市中的总人数,即任一表格中所有元素之和;令 AA 表示非零 ai,ja_{i,j} 的数量;令 BB 表示非零 bi,jb_{i,j} 的数量。

组别 分数 MM SS A,BA,B nn 前置组 备注
0 - - - - - 样例
1 8 S≤7S \le 7 -
2 9 S≤50S \le 50 1
3 8 - A,B≤13A,B \le 13
4 7 A≤13A \le 13 1,3
5 6 m≤50,M≤5000m \le 50, M \le 5000 - -
6 10 M≤5000M \le 5000 5
7 8 M≤50000M \le 50000 n≤1n \le 1 -
8 11 n≤2n \le 2 7
9 5 - - 答案不超过 22
10 6 9 答案不超过 33
11 12 5-10 -
12 10 - 1-11 离线测试