\begin{tutorial}{Разрез таблицы}

Пусть в таблице $k$ единиц. Тогда максимально возможное произведение $\displaystyle \left\lfloor \frac{k}{2} \right\rfloor \cdot \left( k - \left\lfloor \frac{k}{2} \right\rfloor \right)$. Покажем, что ответ всегда достигается. Хотим выделить разрезом часть с $\displaystyle x = \left\lfloor \frac{k}{2} \right\rfloor$. Найдем последнюю строку, что сумма единиц на префиксе строк $\leq x$.

\begin{center}
\renewcommand{\arraystretch}{1.2}
\begin{tabular}{|*{5}{p{1cm}|}}
\hline
\multicolumn{5}{|c|}{} \\
\multicolumn{5}{|c|}{$\leq x$} \\
\multicolumn{5}{|c|}{} \\ \hline
 & & & & \\ \hline
 & & & & \\ \hline
 & & & & \\ \hline
\end{tabular}
\end{center}

В следующей строке возьмем на суффиксе нужное количество элементов чтобы сумма сверху стала равна $x$.

\begin{center}
\renewcommand{\arraystretch}{1.2}
\begin{tabular}{|*{5}{p{1cm}}|}
\hline
\multicolumn{5}{|c|}{} \\
\multicolumn{5}{|c|}{$= x$} \\
\multicolumn{5}{|c|}{} \\ \cline{1-3}
\multicolumn{3}{|c|}{} & \multicolumn{2}{c|}{} \\ \cline{4-5}
& \multicolumn{2}{c}{$=k - x$} & & \\
& & & & \\ \hline
\end{tabular}
\end{center}

После этого разрез восстанавливается из рисунка выше. Асимптотика $\mathcal{O}(n \cdot m)$.

\end{tutorial}
