← 返回题目
题库练习 Table Cut
← 上一题 下一题 →

A16721 | Table Cut

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

给定一个大小为 $n \times m$ 的表格，其中每个单元格中要么是 $0$，要么是 $1$。你的任务是用一条从左上角到右下角的路径将其分为两部分。切割路径只能向右或向下移动。

切割后，令 $a$ 为表格一部分中 $1$ 的个数，$b$ 为另一部分中 $1$ 的个数。你的目标是最大化 $a \cdot b$ 的值。

输入格式

每个测试包含多组测试数据。第一行包含测试用例数量 $t$（$1 \leq t \leq 10^4$）。随后是每个测试用例的描述。

每个测试用例第一行为两个整数 $n$ 和 $m$（$1 \leq n, m \leq 3 \times 10^5$，$2 \leq n \cdot m \leq 3 \times 10^5$）——表格的行数和列数。

接下来的 $n$ 行中，每行有 $m$ 个整数，第 $i$ 行第 $j$ 个数字代表 $a_{i, j}$（$0 \leq a_{i, j} \leq 1$）。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $3 \times 10^5$。

输出格式

对于每个测试用例，输出两行。

第一行输出一个整数，即最大的乘积值。

第二行输出一个由 $n$ 个字符 'D' 和 $m$ 个字符 'R' 组成的字符串，表示切割路径的走法，其中 'D' 表示向下走一步，'R' 表示向右走一步。

输入输出样例

输入 #1
3
5 5
1 0 1 1 0
0 1 0 1 1
1 0 1 0 0
0 1 0 1 0
0 0 0 0 1
5 4
0 0 1 0
0 1 1 1
1 0 0 1
0 1 0 1
0 0 1 0
3 2
1 0
0 1
1 1
输出 #1
30
RDRDRDRDDR
20
DRRDRDDDR
4
DRDRD
C++ 编辑器
输入
输出