TopCoder

Caido
$\text{W}ai\text{M}ai\text{QQ}\sim$

User's AC Ratio

88.9% (32/36)

Submission's AC Ratio

38.8% (40/103)

Tags

Description

東門大地主喜歡割韭菜。

韭菜們排成一個 $n \times m$ 的矩形,從上數來第 $i$ 橫列、由左數來第 $j$ 直行的方格內有一個數字 $a_{ij}$,代表割掉這株韭菜的爽度。東門大地主每次可以割掉「尚未被割的韭菜們形成的矩形」的其中一個邊上(也就是左邊、右邊、上面、下面擇一)的所有韭菜們,而這次割韭菜行動的爽度就是該次被割掉的韭菜的爽度總和;而割完所有韭菜的爽度則是每一次操作的爽度的最大值。

現在,給你韭菜們的爽度,你知道要怎麼割會最爽(爽度最高)嗎?

Input Format

第一行有兩個整數 $n, m$,符合 $1 \leq n, m \leq 1500$
接下來 $n$ 行每行有 $m$ 個整數 $a_{ij}$ ,符合 $-10 ^ 9 \leq a_{ij} \leq 10 ^ 9$。

Output Format

第一行輸出一次操作的最大爽度,第二行輸出一個由 LRUD 四種字元組成的字串,代表每次要割掉韭菜的最左/右/上/下排(定義輸入中第一行最左邊的數字為表格左上角)。按照此字串的步驟執行完之後,所有數字都必須被刪除,且最大爽度的一次操作必須是所有方法中最大的。

若有多種可能的答案,任意一種都會算是對的。

Sample Input

// Sample input 1
3 3
4 -2 5
-10 3 6
4 7 -10

// Sample input 2
2 3
-5 -4 -3
-4 -1 -8

Sample Output

// Sample output 1
11
LLDR

// Sample output 2
-1
URRD

Hints

範例測資一解釋:對於字串"LLDR",四次收割的爽度分別是 $-2, 8, -10, 11$,其中最大值是 $11$ ,而這也是所有方法中最大的。若第二行輸出 "RDUU" 也會被算為正確。

由於本題輸入量較大,建議使用 scanf/printf 或是使用 cin/cout並在程式前面加上 ios_base::sync_with_stdio(0);cin.tie(0);以加快輸入的速度。

Problem Source

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 2 5
3 1000 65536 65536 2 5
4 1000 65536 65536 2 5
5 1000 65536 65536 2 5
6 1000 65536 65536 2 5
7 1000 65536 65536 3 4 5
8 1000 65536 65536 3 4 5
9 1000 65536 65536 3 4 5
10 1000 65536 65536 3 4 5
11 1000 65536 65536 3 4 5
12 1000 65536 65536 3 4 5
13 1000 65536 65536 3 4 5
14 1000 65536 65536 3 4 5
15 1000 65536 65536 3 4 5
16 1000 65536 65536 3 4 5
17 1000 65536 65536 4 5
18 1000 65536 65536 4 5
19 1000 65536 65536 4 5
20 1000 65536 65536 4 5
21 1000 65536 65536 4 5
22 1000 65536 65536 4 5
23 1000 65536 65536 4 5
24 1000 65536 65536 4 5
25 1000 65536 65536 4 5
26 1000 65536 65536 4 5
27 1000 65536 65536 5
28 1000 65536 65536 5
29 1000 65536 65536 5
30 1000 65536 65536 5
31 1000 65536 65536 5