Editorial for COCI '06 Contest 2 #5 Stol
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 ~s_1~ and end in column ~s_2~. For the table to span a certain row, all squares between ~s_1~ and ~s_2~ (inclusive) in that row must be free.
For each row we can determine if there are any blocked squares between columns ~s_1~ and ~s_2~ in constant time: we preprocess the apartment and calculate the number of blocked squares left of each square. Call this number ~sum(row, column)~. After calculating this, the expression ~sum(row, s_2) - sum(row, s_1-1)~ tells us how many squares between ~s_1~ and ~s_2~ 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 ~s_1~ and ~s_2~, giving the largest solution for the assumed columns ~s_1~ and ~s_2~. Exploring all possibilities for ~s_1~ and ~s_2~ we choose the one that gives the maximum perimeter.
The number of possibilities is ~\mathcal O(N^2)~.
Time complexity: ~\mathcal O(N^3)~