## Editorial for COCI '06 Contest 2 #5 Stol

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Suppose one dimension of the table is fixed. For example, let the table start in column and end in column . For the table to span a certain row, all squares between and (inclusive) in that row must be free.

For each row we can determine if there are any blocked squares between columns and in constant time: we preprocess the apartment and calculate the number of blocked squares left of each square. Call this number . After calculating this, the expression tells us how many squares between and are blocked (if this number is zero, then the table can be placed in that row).

A single pass finds the largest consecutive number of rows that don't have walls between and , giving the largest solution for the assumed columns and . Exploring all possibilities for and we choose the one that gives the maximum perimeter.

The number of possibilities is .

Time complexity:

## Comments

There is also an solution to this problem by reducing the problem to largest rectangle in a histogram, and then solving with a monotonic stack. The only modification you need is to use the formula for perimeter instead of area. Example: https://dmoj.ca/src/5742708

(You need this method to pass with Python.)