東門大地主喜歡割韭菜。
韭菜們排成一個 $n \times m$ 的矩形,從上數來第 $i$ 橫列、由左數來第 $j$ 直行的方格內有一個數字 $a_{ij}$,代表割掉這株韭菜的爽度。東門大地主每次可以割掉「尚未被割的韭菜們形成的矩形」的其中一個邊上(也就是左邊、右邊、上面、下面擇一)的所有韭菜們,而這次割韭菜行動的爽度就是該次被割掉的韭菜的爽度總和;而割完所有韭菜的爽度則是每一次操作的爽度的最大值。
現在,給你韭菜們的爽度,你知道要怎麼割會最爽(爽度最高)嗎?
第一行有兩個整數 $n, m$,符合 $1 \leq n, m \leq 1500$
接下來 $n$ 行每行有 $m$ 個整數 $a_{ij}$ ,符合 $-10 ^ 9 \leq a_{ij} \leq 10 ^ 9$。
第一行輸出一次操作的最大爽度,第二行輸出一個由 LRUD
四種字元組成的字串,代表每次要割掉韭菜的最左/右/上/下排(定義輸入中第一行最左邊的數字為表格左上角)。按照此字串的步驟執行完之後,所有數字都必須被刪除,且最大爽度的一次操作必須是所有方法中最大的。
若有多種可能的答案,任意一種都會算是對的。
範例測資一解釋:對於字串"LLDR",四次收割的爽度分別是 $-2, 8, -10, 11$,其中最大值是 $11$ ,而這也是所有方法中最大的。若第二行輸出 "RDUU" 也會被算為正確。
由於本題輸入量較大,建議使用 scanf/printf
或是使用 cin/cout
並在程式前面加上 ios_base::sync_with_stdio(0);cin.tie(0);
以加快輸入的速度。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 2~6 | $a_i \ge 0$ | 7 |
3 | 7~16 | $n, m\le30$ | 25 |
4 | 7~26 | $n, m\le 300$ | 22 |
5 | 2~31 | 無其他限制 | 46 |