#C2376. Largest Fertile Subrectangle
Largest Fertile Subrectangle
Largest Fertile Subrectangle
You are given a rectangular garden represented as a grid of size \(N \times M\). Each cell of the grid is either fertile (denoted by 1
) or infertile (denoted by 0
). Your task is to find the area of the largest contiguous subrectangle (aligned with the grid axes) that contains only fertile cells.
Input: The grid dimensions followed by the grid rows.
Output: A single integer representing the maximum area of a fertile subrectangle.
Note: The subrectangle must be contiguous and consist entirely of 1's.
For example, consider the following grid:
4 5 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
The largest fertile subrectangle has an area of 6.
inputFormat
The first line contains two space-separated integers \(N\) and \(M\), representing the number of rows and columns of the grid respectively.
The next \(N\) lines each contain \(M\) space-separated integers (either 0 or 1) representing the grid.
outputFormat
Output a single integer which is the area of the largest contiguous subrectangle that contains only fertile cells.
## sample4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
6