题目详情题解（0）讨论（0）提交记录（0）

CFCF2205F.Simons and Reconstructing His Roads

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

一直在下落，但我总能找到出口。

—— SHUN, DYING FOR YOU

城市中有 n×mn \times m 个路口，编号为 (1,1),(1,2),…,(n,m)(1, 1), (1, 2),\ldots, (n, m)。第一个数字表示行号，第二个数字表示列号。

仅存在（且只存在）如下两种街道：$ (i,j) $ 与 $ (i+1,j) $ 之间有街道，或 $ (i,j) $ 与 $ (i,j+1) $ 之间有街道。$ (i, j) $ 与 $ (i + 1, j) $ 之间的街道权值为 wi,jw_{i,j}，$ (i, j) $ 与 $ (i, j + 1) $ 之间的街道权值为 vi,jv_{i,j}。

Simons 计划重建一些街道。由于一些事故，有些街道无法被重建，其他的街道可选择性重建。

对于每个路口，如果与其相邻的被重建街道条数为偶数，Simons 将该路口称为“优雅”的。如果所有路口都是优雅的，则称整个重建方案为“优美重建”。

重建方案的美丽度计算如下：

  • 最开始美丽度为 00。
  • 对于每一行 ii 从 11 到 n−1n-1，设本行被重建的街道在第 c1<c2<c3<⋯c_1 < c_2 < c_3 < \cdots 列，则将 wi,c1−wi,c2+wi,c3−wi,c4+⋯w_{i, c_1} - w_{i, c_2} + w_{i, c_3} - w_{i, c_4} + \cdots 累加到美丽度中。
  • 同理，对于每一列 jj 从 11 到 m−1m-1，设本列被重建的街道在第 r1<r2<r3<⋯r_1 < r_2 < r_3 < \cdots 行，则将 vr1,j−vr2,j+vr3,j−vr4,j+⋯v_{r_1, j} - v_{r_2, j} + v_{r_3, j} - v_{r_4, j} + \cdots 累加到美丽度中。

换句话说，如果某条街道在其所属行或列被重建的街道中处于奇数位置，则将权值加到美丽度中；否则减去权值。

例如，下图中的街道和路口均可被重建：


我们可得到如下的优美重建方案：

该重建方案的美丽度为 3+4+2−(−9)−(−2)+9+1−(−1)−(−3)−(−4)=383+4+2-(-9)-(-2)+9+1-(-1)-(-3)-(-4)=38。

请你帮助 Simons，求出所有优美重建方案中美丽度的最大值。

输入格式

每个测试点包含多组测试数据。第一行包含整数 tt，表示测试数据组数（1≤t≤5⋅1041 \le t \le 5\cdot 10^4）。

每组数据第一行包含两个整数 nn 和 mm（2≤n,m≤2⋅1052\le n,m\le 2\cdot 10^5，n⋅m≤4⋅105n\cdot m\le 4\cdot 10^5）——表示行数和列数。

接下来 n−1n-1 行，每行 mm 个整数 wi,jw_{i,j}（−109≤wi,j≤109-10^9\le w_{i,j}\le 10^9），表示 $ (i, j) $ 与 $ (i+1, j) $ 之间的街道权值。

接下来 nn 行，每行 m−1m-1 个整数 vi,jv_{i,j}（−109≤vi,j≤109-10^9\le v_{i,j}\le 10^9），表示 $ (i, j) $ 与 $ (i, j+1) $ 之间的街道权值。

接下来 n−1n-1 行，每行 mm 个字符 pi,jp_{i,j}（pi,j∈{0,1}p_{i,j}\in\{\texttt{0},\texttt{1}\}），若 pi,j=0p_{i,j}=\texttt{0}，表示 $ (i, j) $ 与 $ (i+1, j) $ 之间的街道无法重建，反之可以重建。

接下来 nn 行，每行 m−1m-1 个字符 qi,jq_{i,j}（qi,j∈{0,1}q_{i,j}\in\{\texttt{0},\texttt{1}\}），若 qi,j=0q_{i,j}=\texttt{0}，表示 $ (i, j) $ 与 $ (i, j+1) $ 之间的街道无法重建，反之可以重建。

保证所有测试数据中 ∑n⋅m≤4⋅105\sum n\cdot m \le 4\cdot 10^5。

输出格式

对于每组测试数据，输出一个整数，表示所有优美重建方案中的最大美丽度。

输入输出样例

  • 输入#1

    4
3 4
2 3 -2 3
4 9 4 -4
3 4 -2
-9 -5 1
6 -1 -3
1111
1111
111
111
111
2 4
4 23 1 35
6 12 -17
-14 1 -40
0100
000
101
3 3
1 0 1
0 1 0
1 0
0 1
0 0
110
111
10
11
11
3 4
13 7 6 -12
3 -5 12 -6
-3 10 -15
-5 8 -11
10 0 -5
1111
0110
110
101
010

    输出#1

    38
0
4
8

说明/提示

第一个测试点的解释见描述部分。

第二个测试点中，只有唯一的优美重建方案：Simons 不重建任何街道，所以最大美丽度为 00。

首页