\begin{tutorial}{Bricks in the Wall}

{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Виталий Аксенов\\
         Разработка: & Николай Будин\\
     \end{tabular}
}

Вам дана таблица, заполненная нулями и единицами. Вам нужно найти две непересекающихся полоски (прямоугольника с высотой или шириной равной $1$) из нулей, с максимальной возможной суммарной длиной.

Вычислим значения $d_u[x][y]$, $d_d[x][y]$, $d_l[x][y]$, $d_r[x][y]$ для каждой клетки $(x, y)$~--- длину наибольшей полоски из нулей, начинающейся в клетке $(x, y)$ в направлении вверх/вниз/влево/вправо, соответственно. Эти значения можно вычисить за время $O(n \cdot m)$. Например, можно выделить все максимальные по включению горизонтальные и вертикальные полоски за длину каждой из таких полосок. Либо можно воспользоваться динамическим программированием.

Любые два непересекающихся прямоугольника (с вертикальными и горизонтальными сторонами) можно разделить какой-то вертикальной или горизонтальной прямой. Переберем эту прямую, разделяющую два прямоугольника. Не умаляя общности, пусть мы выбрали горизонтальную прямую. Тогда нужно найти максимальную полоску сверху от этой прямой, и максимальную полоску снизу от этой прямой. Чтобы найти максимальную полоску сверху, нужно взять максимум по всем $d_u[x][y]$ и $d_r[x][y]$ для всех клеток сверху от прямой. Чтобы не перебирать все такие клетки для каждой прямой, будем двигать прямую сверху вниз, при этом множество клеток будет расширяться, и нам нужно будет в максимум добавлять новые значения. Аналогично для полоски снизу от прямой.

И аналогично для вертикальных прямых. Чтобы уменьшить число случаев, можно сначала решить задачу с горизонтальной прямой для исходной таблицы, а потом повернуть таблицу на 90 градусов и ещё раз запустить то же решение.

%You are given a grid of zeroes and ones. And you want to find two non-intersecting stripes (rectangles with a width or a height equal to 1) of zeroes with the maximum possible total length.

%Let's calculate four values $d_u[x][y]$, $d_d[x][y]$, $d_l[x][y]$, $d_r[x][y]$ for every cell $(x, y)$~--- length of the longest stripe starting in the cell $(x, y)$ and going upward/downward/to the left/to the right respectively. These values can be calculated in $O(n \cdot m)$ time.

%Any two non-intersecting rectangles can be divided by some vertical or horizontal line. Let's iterate over all such lines. Without loss of generality, we've chosen a horizontal line. Now we want to find the longest stripe above it and below it. In order to find the length of the longest stripe above the line, you can calculate the maximum over all $d_u[x][y]$ and $d_r[x][y]$ for all cells above the line. And similarly for the part below the line.

\end{tutorial}
