P10719 [GESP202406 Level 5] Black and White Grid.

Related multiple-choice and true/false questions: .

Xiao Yang has a grid with $n$ rows and $m$ columns, where each cell is either white or black. Xiao Yang wants to know how many cells are contained in the smallest sub-rectangle that contains at least $k$ black cells.

The first line contains three positive integers $n, m, k$, with meanings as described in the statement. Then follow $n$ lines, each containing a $\texttt{01}$ string of length $m$, representing the colors of the cells in row $i$ of the grid. If it is $\texttt{0}$, the corresponding cell is white; otherwise, it is black.

Output one integer, representing the number of cells contained in the smallest sub-rectangle that contains at least $k$ black cells. If it does not exist, output $0$.

#### Sample Explanation For sample $1$, let $(i, j)$ represent row $i$ and column $j$. The four vertices of the smallest sub-rectangle that contains at least $5$ black cells are $(2, 4)$, $(2, 5)$, $(4, 4)$, $(4, 5)$, and it contains a total of $6$ cells. #### Constraints For all data, it is guaranteed that $1 \le n, m \le 100$ and $1 \le k \le n \times m$. | Subtask ID | Score | $n, m$ | | :--: | :--: | :--: | | $1$ | $20$ | $\le 10$ | | $2$ | $40$ | $n = 1$, $1 \le m \le 100$ | | $3$ | $40$ | $\le 100$ | Update on 2024/7/9: Several groups of hack testdata were added. Thanks to @cff_0102 for the contribution. Translated by ChatGPT 5