Largest Rectangular Area of Plants in a Grid

During the harvest festival in a small village, a peculiar game is played in a special garden. The garden is arranged as an (N \times N) grid where each cell either contains a plant (denoted by 1) or is empty (denoted by 0). The objective is to identify the largest rectangular area that is completely filled with plants.

A typical approach involves treating each row as the base of a histogram and then using a stack-based method to compute the largest rectangle for that histogram. The final answer is the maximum rectangular area found over all rows.

This problem requires reading input from standard input (stdin) and printing output to standard output (stdout).

inputFormat

The first line contains a single integer (N), the size of the garden grid. The following (N) lines each contain (N) integers separated by spaces, where each integer is either 0 or 1, representing an empty cell or a cell with a plant.

outputFormat

Output a single integer which is the size (area) of the largest rectangular region in the grid that is completely filled with plants.## sample

5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
1 1 1 0 0

6