Для того, чтобы решить первую подзадачу, переберем размер креста и его левый-верхний угол центрального квадрата креста и проверим, что каждая из клеток зафиксированного креста пригодна для строительства. Такое решение работает за O(n3·m2)и проходит первую подзадачу.
Улучшим данное решение, заметим что если мы зафиксировали левый-верхний угол центрального квадрата креста и можно построить крест размера k с ним, то с ним можно построить и крест любого меньшего размера, так как множество креста меньшего размера будет подмножеством клеток креста большего размера с ним. А значит будет работать такое решение переберем левый-верхний угол центрального квадрата креста и будем пытаться увеличить ответ, пока это возможно, проверяя, что каждая из клеток зафиксированного креста пригодна для строительства, так же, как в прошлой подзадаче. Такое решение работает за O(n2·m2) и проходит первые 2 подзадачи.
Улучшим первое решение по-другому, заметим, что проверять то, что каждая из клеток зафиксированного креста пригодна для строительства, равносильна проверке, что число клеток пригодных для строительства в каждом из 5 квадратов креста равно квадрату размера креста. Это легко проверяется за O(1) с помощью префиксных сумм. Такое решение работает за O(n2·m). И проходит первые 3 подзадачи.
Скомбинировав идеи предыдущих двух подзадач получаем решение, работающее за O(n·m), которое проходит все тесты.