2274 . 割韭菜

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

83.8% (67/80)

Submission's AC Ratio

27.8% (80/288)

Tags

CKcon 2022-CKcon

Description

東門大地主喜歡割韭菜。

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

現在，給你韭菜們的爽度，你知道要怎麼割會最爽（爽度最高）嗎？

Input Format

第一行有兩個整數 n,m，符合 1≤n,m≤1500
接下來 n 行每行有 m 個整數 aij ，符合 −109≤aij≤109。

Output Format

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

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

Sample Input 1

3 3
4 -2 5
-10 3 6
4 7 -10

Sample Output 1

11
LLDR

Sample Input 2

2 3
-5 -4 -3
-4 -1 -8

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 ai≥0 7
3 7~16 n,m≤30 25
4 7~26 n,m≤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
Submit
Back to Top