Puzzle of 1's and 0's

If you see the constraints of this problem, you can see the the width of the puzzle board is significantly small. It is so small that you can run iterations on each range of consecutive columns.

Lets try to solve this problem for P=0 first.

Let there be some board with width 10. We will see how to check if our biggest rectangle starts in 4th column and ends in 6th column.

- - - x x x - - - -
- - - x x x - - - -
- - - x x x - - - -
- - - x x x - - - -
- - - x x x - - - -

In this checking, we have fixed the left bound and the right bound for our rectangle. Now, we have to find such upper and lower bounds, so that there is no 0 in between (as we are solving for P=0). There will be multiple such upper and lower bounds for the taken range of columns (4th to 6th).
We will take the bounds that contain the largest.

Let the board be like this:

- - - 1 0 1 - - - -
- - - 1 1 1 - - - -
- - - 0 1 1 - - - -
- - - 1 1 1 - - - -
- - - 1 1 1 - - - -
- - - 1 1 0 - - - -

Now we have two bounds (left and right) fixed for our rectangle. We will now iterate for another bound to fix, let that be the lower bound.

- - - 1 0 1 - - - -
- - - 1 1 1 - - - -
- - - 0 1 1 - - - -
- - - 1 1 1 - - - -
- - - 1 1 1 - - - -
- - - x x x - - - -

Lets say, we are here, fixing the lower bound at 5, we have to find the upper bound for which there will be no 0 in between, and the upper bound will be as high as possible.

Look at this example and you will understand that the best upper bound in this case is 4. Because, from row 4 to 5, there is no 0; and it is the maximum rectangle possible.

similarly, for lower bound = 2, upper bound would have to be 2 as well.

Now, how to find this upper bound efficiently?
If you pre-calculate the number of zeros a row has within your column range, then you can also keep a cumulative count for them.
Now, as the cumulative count is a non decreasing sequence, you can run a binary search and find out the top most row for which, the difference of the cumulative count between that row and the lower bound is 0. This guarantees that there is no 0 in between.

This is the solution for p = 0.

What will happen when p > 0?
Well, easy.
In the binary search, you will have to find out the top most row for which, the difference of the cumulative count between that row and the lower bound is <= p.