Table Cut

Let $T$ be the total number of ones in the table. If one part contains $s$ ones, the other contains $T-s$, so the value is

$$s(T-s).$$

This parabola is maximized when $s$ is as close as possible to $T/2$. Therefore the best possible answer is

$$\left\lfloor \frac T2 \right\rfloor \left\lceil \frac T2 \right\rceil.$$

The real question is whether we can always construct a valid cut with exactly

$$k = \left\lfloor \frac T2 \right\rfloor$$

ones on one side. Yep. The table looks scary, but the construction is honestly pretty blunt.

Describe a cut by values $x_1,x_2,\dots,x_n$, where $x_i$ is the number of cells taken from the left side of row $i$. A valid monotone path requires

$$0 \le x_1 \le x_2 \le \dots \le x_n \le m.$$

Now use a very restricted shape:

• rows above some row take $0$ cells,
• one row takes a prefix,
• rows below it take all $m$ cells.

This is valid because the sequence looks like

$$0,0,\dots,0,c,m,m,\dots,m,$$

which is nondecreasing. No weird DP needed. Nice.

Scan rows from bottom to top while counting how many ones are already included from fully taken lower rows. Suppose this count is below.

For the current row:

• if below + rowOnes < k, then even taking the whole row is not enough, so set this row to full and continue upward;
• otherwise, the target lies inside this row. We need

$$need = k - below$$

ones from a prefix of the current row.

Because the row contains only $0$ and $1$, its prefix-one count starts at $0$ and increases by exactly $1$ whenever we pass a one. So every value from $0$ to rowOnes appears as some prefix count. Pick the first column where the prefix has exactly need ones.

Then set:

• all rows above to $0$,
• this row to that prefix length,
• all rows below to $m$.

That chosen side has exactly $k$ ones, so the product is optimal.

Finally, convert the prefix lengths into the output path. Start at column $0$. For each row $i$, move right until the current column equals $x_i$, then move down once. After all rows, move right until column $m$.

Since the $x_i$ are nondecreasing, this never asks the path to move left. The output has exactly $n$ D moves and $m$ R moves.

Edge cases are clean:

• If $T=0$ or $T=1$, then $k=0$ and the best product is $0$.
• If the target is already reached by lower rows, choose a prefix of length $0$ in the next row.
• Single-row and single-column tables work with the same logic.

The algorithm reads the table once, scans rows once, and builds a path of length $n+m$. Complexity is

$$O(nm)$$

per test case, with $O(nm)$ memory for storing the table. This fits because the total number of cells over all test cases is at most $3\cdot 10^5$.