← 返回题目列表

Codeforces · 2194/D

D. 桌子切割

中文机器翻译题面 查看原题

给定一个大小为 $$$n \times m$$$ 的表格,其中每个单元格包含 $$$0$$$ 或 $$$1$$$。任务是将其分成两部分,并从左上角到右下角进行切割。切割线只能向右或向下。

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

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 3 \cdot 10^{5}$$$, $$$2 \leq n \cdot m \leq 3 \cdot 10^{5}$$$) - 分别是表中的行数和列数。

以下 $$$n$$$ 行中的每一行都包含 $$$m$$$ 整数,其中 $$$i$$$ 第 $$$i$$$ 行中的第 $$$j$$$ 数字对应于值 $$$a_{i, j}$$$ ($$$0 \leq a_{i, j} \leq 1$$$)。

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

输出

对于每个测试用例,在输出数据的第一行输出一个数字——乘积的最大值。

在第二行中,输出由 $$$n$$$ 个字符组成的字符串 'D' 和 $$$m$$$ 个字符 'R',代表下一次切割的方向,其中'D' 表示向下切割,并且 'R' — 向右剪切。

示例

输入
复制

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

输出
复制

30
RDRDRDRDDR
20
DRRDRDDDR
4
DRDRD

注意

图像显示了第一个和第二个测试用例的正确切割,此时实现了产品的最大值。