Пусть мы нашли прямоугольник, в котором столько же деревьев, сколько в оптимальном ответе. Понятно, что сверху он упирается в какой-то прямоугольник, т.к. в противном случае, сдвинем его вверх и улучшим ответ. Аналогичные рассуждения проведем и для сдвига влево. Теперь переберем пару прямоугольников и предполагаем, что наш ответ упирается в первый сверху/снизу, а во второй справа/слева. То есть у нас есть O(K^2) кандидатов на ответ. Перебираем их все и за O(K) считаем сколько в них деревьев. Итоговая сложность O(K^3).

скорее всего нет.

Вряд ли кто из участников выложит. Разве что жюри. Просто архива нет. 17 января должны на http://dl.gsu.by/ выложить.

тут есть 3 случая. Если из кого либо числа извлекается квадратный корень то он ответ. так же если мы разложим число на простые множители до 10^6 и степень одного из них больше 1 то ответ этот простой делитель. дальше смотрим все пары и их нод. если нод не 1 то ответ будет наш нод. Почему можно смотреть делитель до миллиона. Ну так как простых делителей больших кубического корня будет строго меньше 3.