Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Puzzle of 1's and 0's

By mainstring · Limits 1s, 512 MB

There is a rectangular puzzle board containing N×MN \times Mnumber of places. Each place contains a number: either 11 or 00.

You are given P number of extra 22 ’s. You can replace any of the numbers on the board with your extra 22 ’s.
For each of your extra 22 ’s, you can either use it on the board only once, or not use it at all.
You can not re-use the removed numbers from the board.

After replacing, you have to determine the biggest rectangle on the board which doesn’t contain any 00.

Input

The first line of input contains 3 numbers: NN, MM, PP where ( 1N1051 \leq N \leq 10^5, 1M101\leq M \leq 10, 0P100 \leq P \leq 10).

Each of next NN lines contain MM integers. Each integer is either 11 or 00.

Output

Print 11 number: the area of the biggest rectangle that does not contain any 00.

Samples

InputOutput
6 10 0
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1 0
0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 1 1 1 1 0
9
InputOutput
6 10 2
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1 0
0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 1 1 1 1 0
12

Discussion

Statistics


94% Solution Ratio

prodip_bsmrstuEarliest, 1M ago

Zihad_BdFastest, 0.1s

BrehamPieLightest, 4.1 MB

serotoninShortest, 835B

Submit

Login to submit

Editorial

If you see the constraints of this problem, you can see the the width of the puzzle board is signifi...

Toph uses cookies. By continuing you agree to our Cookie Policy.