Данная задача предполагает множество различных решений. Самые элементарные из них (для удобства оценки будем считать, что \(n=\max(w,h)\)):

\(O(n^{10})\)

Перебрать участок, который следует удобрить (он представляет собой прямоугольник, всего \(O(n^4)\) вариантов), перебрать итоговый участок посадки (он также представляет собой прямоугольник, \(O(n^4)\) вариантов), далее проверить корректность (возможность совершить посадку) за \(O(n^2)\). Такое решение, представляющее собой перевод условия на язык программирования, набирало 10 баллов.

\(O(n^6)\) (первое решение, простое)

Перебрать фрагмент для посадки (больший прямоугольник, \(O(n^4)\) вариантов). Осталось для каждого проверить, можно ли удобрить какой-то подпрямоугольник так, чтобы весь фрагмент состоял из единиц. Это делается за \(O(n^2)\) — найдём нули с самыми больши́ми и маленькими номерами строк и столбцов (всего 4 числа) — это границы искомого подпрямоугольника.

\(O(n^6)\) (второе решение)

Перебрать ход (меньший прямоугольник, \(O(n^4)\) вариантов), затем найти оптимальный удобренный участок за \(O(n^2)\). Вторая часть решения является классической задачей, которая решается следующим образом. Зафиксируем нижнюю границу, затем будем перебирать вертикальные столбцы слева направо, храня столбцы в стеке. При добавлении очередного столбца из стека следует удалить все столбцы, бо́льшие текущего, проверяя прямоугольник, ограниченный удаляемым и добавляемым столбцами. Высоты столбцов можно предварительно подсчитать методом динамического программирования. Такое решение даже при самой неоптимальной реализации работало для \(w\) и \(h\) до 40 и набирало 30 баллов. Добавление отсечений или технических оптимизаций могло незначительно улучшить результат.

\(O(n^4)\)

Зафиксировать границы прямоугольника-ответа (\(O(n^4)\) вариантов), затем проверить, что неудобренные клетки внутри образуют прямоугольник. Для того, чтобы эта проверка выполнялась за \(O(1)\), нужно при переходе от одного прямоугольника к другому пересчитывать количество неудобренных клеток внутри, а также позиции крайних таких клеток. Такое решение работало для \(w\) и \(h\) порядка 100 и набирало около 50 баллов в зависимости от реализации. Также к нему можно добавить отсечения, главное из которых — при фиксированных трёх границах прерывать перебор, если теоретически получаемый ответ меньше текущего (отсечение по ответу).

\(O(n^3)\)

Зафиксировать верхнюю и нижнюю границы ответа (\(O(n^2)\) вариантов). Заметим, что теперь все столбцы, содержащие неудобренные клетки, должны содержать их на одних и тех же позициях, а также быть расположенными подряд. Поэтому можно перебрать левую и правую границу ответа методом двух указателей за \(O(n)\). Такое решение работало для \(w\) и \(h\) до 300 и набирало 60 баллов.

Следующие решения являются значительными продвижениями к верному и набирают от 80 баллов.

\(O(n^2\cdot\log n)\)

Развитие предыдущего решения. Зафиксируем нижнюю границу (\(O(n)\) вариантов). Теперь рассмотрим группы полосок с одинаковыми позициями нулей. При движении верхней границы эти группы будут разделяться (в случае, когда позиции нулей перестали совпадать), либо исчезать (когда группа нулей в столбце перестаёт быть непрерывной). Всего таких событий \(O(n)\), так как они происходят не более одного раза для каждого столбца и не более одного раза для каждой пары соседних столбцов. Можно поддерживать дерево, либо другую структуру данных, поддерживающую эти операции за \(O(\log n)\).

\(O\bigl(n^2\cdot\alpha(n)\bigr)\)

Развитие предыдущего решения. Будем двигать верхнюю границу в обратном направлении. В таком случае события разделения заменяются событиями объединения, поэтому можно использовать систему непересекающихся множеств.