codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/bf5a95bd1bfc341b05232d999b0048817fc8b08f.png) ![](https://espresso.codeforces.com/9e50e43cf6573882647584be3bda8171ba34d3f0.png)