#K73567. Maximum Rectangle Area in a Grid

    ID: 34004 Type: Default 1000ms 256MiB

Maximum Rectangle Area in a Grid

Maximum Rectangle Area in a Grid

You are given a grid of size n rows and m columns. Each cell in the grid is either empty (denoted by 0) or blocked by an obstacle (denoted by 1). Your task is to find the maximum area of a rectangle that can be formed using only empty cells (0's).

Note: The rectangle must be contiguous and its sides should be parallel to the grid axes.

Input Format: The first line contains two integers n and m, representing the number of rows and columns, respectively. This is followed by n lines each containing m space-separated integers (either 0 or 1) representing the grid.

Output Format: Output a single integer representing the maximum area of the rectangle consisting entirely of 0's. Output should be printed to stdout.

inputFormat

The input is read from stdin and has the following format:

Line 1: Two integers n and m, representing the number of rows and columns. Next n lines: Each line contains m space-separated integers (0 or 1) representing the grid.

outputFormat

Print a single integer to stdout that denotes the maximum area of a rectangle containing only 0's.## sample

1 4
0 1 0 0
2