Дана таблица $$$n \times m$$$, в каждой ячейке таблицы записан $$$0$$$ или $$$1$$$. Требуется разделить её на две части разрезом, проходящим из левого верхнего угла в правый нижний. Линии разреза могут идти только вправо или вниз.
Пусть $$$a$$$ — количество единиц в одной части таблицы после разреза, $$$b$$$ — количество единиц в другой части таблицы. Требуется максимизировать величину $$$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$$$ целых чисел, $$$j$$$-е число в $$$i$$$-й из этих строк соответствует значению $$$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
На рисунках изображены корректные разрезы для каждого первого и второго набора входных данных, при которых достигается максимальное значение произведения.
| Codeforces Round 1078 (Div. 2) |
|---|
| Закончено |
