CF2194D Table Cut

给定一个大小为 $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' 表示向右走一步。

下方所示图片为每个测试用例前两组数据的最佳切割，均能获得最大乘积值。   由 ChatGPT 5 翻译