\begin{tutorial}{Мадока и порванный фотоальбом}

Решим вначале другую задачу. Пусть нам известны, клетки, которые мы вырезали. Нужно проверить, правда ли, что можно их вырезать прямоугольниками, которые не пересекаются и не касаются.

Утверждение: в любом квадрате $2 \times 2$ не может быть вырезано 3 прямоугольника. Интуиция следующая --- если это так случилось, то мы получили угол, в котором они должны касаться.

Теперь решим исходную задачу. Пусть $dp_{i, mask}$ --- это максимальная площадь корректного разреза, если мы рассматриваем только первые $i$ столбцов, а в последней строке мы вырезали только клетки в строках, где в битовом представлении $mask$ стоит единица, а если это состояние недостижимо, то в нем стоит $-\inf$. Тогда нужно научиться пересчиывать эту динамику.

Давайте вначале разберемся, в каком случае у нас может быть в $i$ столбце маска $mask_1$, а в $i + 1$ столбце маска $mask_2$. И при этом разрез корректный. Вспоминаем прошлую задачу. И понимаем, что во всех квадратах $2 \times 2$ не должно быть три вырезанных клетках, а также состояние с $mask_1$ достижимо, а в $mask_2$ нет заблокированных клеток.

Тогда $dp_{i, mask} = max(cntbit(mask) + dp_{i - 1, mask_1}$ по всем возможным $mask_1$, где можно по предыдущему пункту иметь две подряд идущие маски эти. А $cntbit(mask)$ --- это количество единичных битов в числе.

И итоговая асимтотика $O(4^n \cdot n \cdot m)$, так как проверка для двух масок происходит за $O(n)$, а всего масок $2^n$.

\end{tutorial}
