| Algo Cup 2025 by csspace.io (Финал) |
|---|
| Закончено |
Вам дана матрица размера $$$n \times m$$$, состоящая из целых положительных чисел.
Вы можете выбрать любую начальную клетку матрицы. За один ход вы перемещаетесь либо вниз, либо вправо в матрице. При этом ход из ячейки $$$(n, j)$$$ матрицы вниз перемещает вас в ячейку $$$(1, j)$$$, а ход из ячейки $$$(i, m)$$$ вправо перемещает вас в ячейку $$$(i, 1)$$$.
Ваша задача — сделать ровно $$$n$$$ ходов вниз и ровно $$$m$$$ ходов вправо и вернуться в изначальную клетку так, чтобы никакая клетка матрицы не была посещена дважды (кроме начальной). Найдите такой способ выбрать начальную клетку и сделать $$$n+m$$$ ходов, как описано выше, чтобы сумма чисел в пройденных клетках была максимальна.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 1\,500$$$) — размеры матрицы.
Следующие $$$n$$$ строк содержат по $$$m$$$ целых положительных чисел, $$$i$$$-я из этих строк содержит числа $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ ($$$1 \le a_{i, j} \le 1\,000\,000$$$) — числа в $$$i$$$-й строке матрицы.
В первой строке выведите максимальную сумму, которую возможно набрать с помощью $$$n$$$ ходов вниз и $$$m$$$ ходов вправо.
Во второй строке выведите два числа $$$r$$$ и $$$c$$$ — номер строки и номер столбца стартовой ячейки в оптимальном способе.
В последней строке выведите строку из $$$n+m$$$ символов, состоящую из ровно $$$n$$$ символов 'D' и ровно $$$m$$$ символов 'R', соответствующую оптимальной последовательности ходов. Символ 'D' соответствует ходу вниз, символ 'R' соответствует ходу вправо.
Если ответов несколько, выведите любой из них.
2 21 23 4
10 1 1 DRDR
3 31 2 34 5 67 8 9
37 1 2 DRDRRD
3 39 1 19 9 99 1 1
46 1 1 DRRDRD
3 774 68 24 42 27 1 8157 67 49 40 1 92 8334 88 86 45 32 48 24
613 1 2 DDRRRRRDRR
| Название |
|---|


