2194D.md (2084B)
1 Source: https://codeforces.com/problemset/problem/2194/D 2 3 D. Table Cut 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Given a table of size $n \times m$, where each cell contains either $0$ or $1$. The task is to divide it into two parts with a cut that goes from the top left corner to the bottom right corner. The cut lines can only go right or down. 22 23 Let $a$ be the number of ones in one part of the table after the cut, and $b$ be the number of ones in the other part of the table. The goal is to maximize the value of $a \cdot b$. 24 25 Input 26 27 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 28 29 The first line of each test case contains two integers $n$ and $m$ ($1 \leq n, m \leq 3 \cdot 10^{5}$, $2 \leq n \cdot m \leq 3 \cdot 10^{5}$) — the number of rows and columns in the table, respectively. 30 31 Each of the following $n$ lines contains $m$ integers, where the $j$-th number in the $i$-th line corresponds to the value $a_{i, j}$ ($0 \leq a_{i, j} \leq 1$). 32 33 It is guaranteed that the sum of $n \cdot m$ across all test cases does not exceed $3 \cdot 10^{5}$. 34 35 Output 36 37 For each test case, output a single number in the first line of the output data — the maximum value of the product. 38 39 In the second line, output a string consisting of $n$ characters 'D' and $m$ characters 'R', representing the direction of the next cut, where 'D' means a cut downwards, and 'R' — a cut to the right. 40 41 Example 42 43 Input 44 45 ``` 46 3 47 5 5 48 1 0 1 1 0 49 0 1 0 1 1 50 1 0 1 0 0 51 0 1 0 1 0 52 0 0 0 0 1 53 5 4 54 0 0 1 0 55 0 1 1 1 56 1 0 0 1 57 0 1 0 1 58 0 0 1 0 59 3 2 60 1 0 61 0 1 62 1 1 63 ``` 64 65 Output 66 67 ``` 68 30 69 RDRDRDRDDR 70 20 71 DRRDRDDDR 72 4 73 DRDRD 74 ``` 75 76 Note 77 78 The images show the correct cuts for each of the first and second test cases, at which the maximum value of the product is achieved. 79 80  