Пишем алгоритм за квадрат. Очевидно, если $$$i$$$ зафиксировано — мы можем набирать нашу последовательность $$$b$$$ жадно. Теперь перейдём от $$$i$$$ к $$$i+1$$$. Если $$$i$$$ было нашим $$$b_1$$$, посмотрим на ближайшее число справа равное $$$b_1$$$. Если оно дальше, чем $$$b_2$$$, посмотрим на ближайшее от этого $$$b_1$$$ справа, равное $$$b_2$$$. И так далее, если сейчас $$$b_i$$$, проверяем, что $$$b_{i+1}$$$ левее $$$b_i$$$, и если да — ищем новое $$$b_{i+1}$$$ справа.

Можно создать $$$map$$$ с позициями чисел в $$$a$$$ для каждого значения — тогда искать ближайшее справа можно за $$$\log(n)$$$ бинпоиском.

А теперь поймём, что это не квадрат, а линия. Заметим, что после каждого шага у нас двигается вправо указатель на $$$b_{i+1}$$$. А суммарный размер всех массивов с ними $$$\leqslant n$$$. Значит, работает за $$$O(n\log(n))$$$.

Делаем центроидную декомпозицию на $$$1$$$ дереве. Перебираем центроид, а внутри вершину. Теперь для этой вершины в центроидной декомпозиции $$$2$$$ дерева есть всего логарифм предков-центроидов. Переберём их — получаем (вершина; $$$2$$$ центроида, через которые идут пути). И таких пар у нас $$$n\log(n)^2$$$. И при этом мы знаем расстояние от вершины до двух этих центроидов. Тогда длина пути (который проходит через эти $$$2$$$ центроида) — просто сумма расстояний для $$$2$$$ вершин-концов этого пути.

Ну и всё, просто для каждой полученной так пары центроидов сохраняем $$$2$$$ вершины с минимальным расстоянием до них. И, взяв минимум сумм по всем, получаем ответ. Сложность $$$O(n\log(n)^2)$$$, но достаточно чистый (если аккуратно написать) — я загнал на $$$99$$$ баллов.

Сделаем центроидную декомпозицию в $$$1$$$ дереве, переберём центроид. Теперь хотим узнать минимум из всех попарных расстояний его детей. Зафигачим сжатое дерево из них во $$$2$$$ графе. У каждой вершины есть вес — её высота до центроида в $$$1$$$ дереве, у каждого ребра есть длина. Надо найти минимальную пару по (вес в вершинах+вес пути) в нашем сжатом дереве. Это делается переподвешиваниями стандартно. И было бы $$$O(n\log(n))$$$, если бы не построение сжатого дерева.

В ней у нас лишний $$$\log(n)$$$ от поисков $$$LCA$$$ — но мы зафигачим спарсы, и он уйдёт. И ещё лишний $$$\log(n)$$$ от сортировки вершин по $$$tin/tout$$$. Но если сохранять отсортированность при переходе в сыновей во время центроидной декомпозиции (тоже стандартно делается) — можно добиться желаемого $$$O(n\log(n))$$$. Но, кстати, с сортировкой за $$$O(n\log(n)^2)$$$ всё равно быстрее :)

Ну, точнее, комбинация этих подходов — $$$2$$$ массива мы пересчитываем и сохраняем отсортированными при переходе в сыновей, а $$$1$$$ массив (c $$$LCA$$$) сортируем заново. Так у меня получалось быстрее всего — и зашло, в итоге, на $$$99$$$ баллов.

Делаем бинпоиск по ответу. Если мы ищем $$$2$$$ касающиеся окружности радиуса $$$r$$$ без ёлок внутри — это то же самое, что искать отрезок длины $$$2r$$$, с концами не внутри окружностей радиуса $$$r$$$, надутых из каждой ёлки (ну, и не вне прямоугольника со сторонами, урезанными на $$$r$$$).

Ниже идёт лирическое отступление, можно сказать так: Заметим, что для заданного радиуса $$$r$$$ можно проверять только отрезки вида (точка на пересечении $$$2$$$ объектов — точка на объекте (сторона/окружность)). Но тогда это будет кукарек :)

Пусть отрезок такой есть. Будем его двигать влево, пока он не коснётся вершиной окружности/стороны. Теперь начнём поднимать его вверх (двигая по этой стороне/окружности), пока можем. Если он на верхней точке — убираем с объекта, продолжая двигать влево. Иначе он либо встал $$$1$$$ вершиной на пересечении $$$2$$$ объектов, либо стал каждой вершиной на какой-то объект (возможно, совпадающие).

Если он каждой вершиной на каком-то объекте — продолжим двигать отрезок. Можно представлять, что мы двигаем окружность радиуса $$$2r$$$ по объекту. И вторая точка находится на пересечении её объекта и этой окружности. Если пересечения нет — отлично, мы "снялись" с того объекта, продолжаем алгоритм.

Хорошо, значит, когда наш мысленный алгоритм завершится, у нас будет вершина на пересечении $$$2$$$ объектов. Окей, начнём двигать $$$2$$$ вершину по окружности радиуса $$$2r$$$, с центром в нашей точке. Она остановится, когда попадёт на какой-то объект (сторону/окружность). Заметим, что диаметральная точка нашей окружности $$$1$$$ точки (или точка нашей стороны на расстоянии $$$2r$$$), в частности подходят (если не принадлежат другим объектам, на которые мы натолкнёмся раньше.

Отлично, мы доказали мысленным алгоритмом, что, если существует такой отрезок длины $$$2r$$$, то существует отрезок, у которого $$$1$$$ точка на пересечении $$$2$$$ объектов (окружностей/прямых), а вторая ещё на каком-то. Причём, если мы зафиксируем объекты, $$$1$$$ точка получается с точностью до $$$2$$$ и $$$2$$$ точка тоже — пересечение окружности радиуса $$$2r$$$ с центром в $$$1$$$ точке и того объекта.

Продолжение решения.

Теперь переберём все варианты, проверка, что отрезок подходит втупую за $$$O(n)$$$ — проверяем все окружности, что точка не лежит в них. Есть решение за $$$O(n^4\log(C))$$$ — заходит на $$$52$$$ балла.

Теперь единственный кукарек. Заметим, что точек вида (пересечение $$$2$$$ объектов), которые не лежат внутри другого объекта (а нам подходят в качестве центра НЛО только такие) порядка $$$O(n)$$$. Сразу получаем сложность $$$O(n^3\log(C))$$$, которая набирает $$$66$$$ баллов.

Теперь хотим за быстро проверять, что точка не принадлежит окружностям. Тогда получим решение за $$$O(n^2\log(C)\cdot check)$$$ — так как сначала перебираем пересечение, проверяем, что оно хорошее — и уже для $$$O(n)$$$ оставшихся вариантов перебираем объект, на котором второй центр.

Хорошо, точки для проверки лежат хотя бы на $$$1$$$ из окружностей, которые у нас есть (с центрами в ёлках радиуса $$$r$$$) или сторон прямоугольника. Надо для каждой окружности насчитать, какие точки хорошие, а какие — нет.

Просто переберём другие объекты, посчитаем пересечениями, какие отрезки плохие (лежат внутри второго объекта), теперь отсортируем, и оставим отрезки, которых тут нет. Можно сделать сканлайном легко. (Для окружностей удобно разделить всё на верхние точки и нижние, и делать всё независимо — тогда нужна только $$$x$$$-координата для проверки, что точка хорошая).

И теперь просто бинпоиском для точки проверяем, принадлежит ли она хорошему отрезку. Получаем сложность решения $$$O(n^2\log(C)\log(n))$$$, если верить в кукарек. И я смог загнать это на $$$100$$$ баллов :)

Обозначим за $$$row_i$$$ — сумму в $$$i$$$-ом столбце, и $$$col_j$$$ — в $$$j$$$-ой строке.

Обозначим за $$$M$$$ — максимальное число элементов в ответе в одной строке/столбце (очевидно, $$$M \leqslant k$$$).

Обозначим за изолированный тот элемент ответа, у которого нет соседних с ним по строке/столбцу других элементов ответа. В частности, значение в нём будет просто $$$row_i+col_j-3a_{ij}$$$.

Сначала я опишу основные идеи, которые мы будем применять в решении, а потом предложу свой вариант их склейки в 100 баллов — тут уже всё может быть сильно вариативно :)

(Правда, из-за плохих претестов моё решение, в итоге, за-WA-шилось, так что проверить оптимальность не получится — набирает только 78 баллов :(

\begin{enumerate} \item Возьмём оптимальный ответ. Посмотрим на любую строчку $$$i$$$ в нём, пусть в ней взято $$$t > 0$$$ клеток.

Заметим, что каждая взятая клетка вычитает из остальных $$$(t+2)a_{ij}$$$ и прибавляет к себе ($$$\leqslant row_i+col_j$$$). (Если мы взяли какие-то ещё числа из того же столбца — $$$col_j$$$ будет только уменьшаться).

Хорошо, $$$row_i$$$ у всех одинаковое, значит, возьмём эту строчку $$$i$$$ и заранее отсортируем все элементы в ней по $$$col_j-(t+2)a_{ij}$$$.

Пусть какой-то элемент не входит в первые $$$k$$$ из них. Тогда оставшиеся $$$k-1$$$ элемент могут занять максимум $$$k-1$$$ столбец, то есть, минимум $$$1$$$ элемент из этих первых $$$k$$$ будет одинок в своём столбце.

Заменим наш элемент (не входящий в первые $$$k$$$) на этот. Заметим, что $$$col_j-(t+2)a_{ij}$$$ стало, а было ($$$\leqslant col_x-(t+2)a_{ix}$$$), и по условию отсортированности $$$col_x-(t+2)a_{ix} \leqslant col_j-(t+2)a_{ij}$$$. Значит, сумма не уменьшилась, ведь всё остальное не изменилось (или увеличилось: если какие-то элементы ответа стояли в столбце $$$x$$$ — к ним дополнительно прибавилось $$$a_{ix}$$$).

\item Теперь будем повторять наш алгоритм (делать замену элемента в ответе), пока можем. И, в итоге, получаем, что, если в строке ровно $$$t$$$ элементов, для этих элементов у нас только $$$k$$$ вариантов. Ну, то есть, существует ответ, который состоит только из этих $$$k$$$ вариантов.

При этом $$$t$$$ у нас от $$$1$$$ до $$$M$$$. Значит, в строке могут подходить в качестве элементов ответа не больше $$$Mk$$$ вариантов (первые в порядке сортировке по $$$col_j-(t+2)a_{ij}$$$ по всем $$$1 \leqslant t \leqslant M$$$).

И абсолютно аналогично в столбце. Итого, у нас уже не $$$nm$$$ вариантов для элементов ответа, а $$$\leqslant Mk\cdot\min(n, m) \leqslant k^2\cdot\min(n, m)$$$.

Назовём эти элементы множеством кандидатов.

\item Пусть $$$C = (2Mk-1)(k-1)+1$$$. Смысл поймём чуть позже.

Посмотрим на элемент из кандидатов. У каждого такого элемента по не больше $$$Mk$$$ соседей кандидатов в строке и в столбце. Значит, если мы его возьмём, у нас обретут соседа не больше $$$2Mk-1$$$ элементов-кандидатов (включая его самого).

Теперь посмотрим на первые $$$C$$$ элементов в порядке сортировки кандидатов по $$$row_i+col_j-3a_{ij}$$$. Пусть в ответе есть элемент, не входящий в них. Тогда каждый из $$$k-1$$$ остальных элементов ответа имеет соседями по не больше $$$2Mk-1$$$ элементов. И остаётся хотя бы $$$1$$$ изолированный из этих $$$C$$$ первых.

Заменим наш (не входящий в первые $$$C$$$) элемент на этот изолированный. Заметим, что сумма не уменьшилась, так как наш элемент давал в сумму $$$\leqslant row_x+row_y-3a_{xy}$$$ (с дополнительными вычитаниями, если был с кем-то в одной строке/столбце), что из отсортированности $$$\leqslant row_i+row_j-3a_{ij}$$$ (без вычетаний по определению изолированности).

\item Отлично, будем повторять это, пока можем. В итоге, аналогично $$$2$$$ пункту, получим, что существует ответ, где все элементы его принадлежат этим $$$C$$$ первым элементам, базово просто $$$(2k^2-1)(k-1)+1$$$ элементам.

Это теперь наше новое множество кандидатов.

\item Пусть мы уже перебрали $$$t$$$ вершин, которые мы считаем, что входят в ответ. Поставим в эти клетки $$$0$$$ и будем поддерживать актуальные $$$row_i$$$ и $$$col_j$$$. Также для каждой строки/столбца будем считать кол-во уже взятых элементов в них — $$$numrow_i$$$ и $$$numcol_j$$$.

Теперь, если мы взяли в ответ ещё и элемент $$$a_{ij}$$$, мы должны дополнительно вычесть $$$(numrow_i+numcol_j)a_{ij}$$$, потому что он вычитается из значения всех уже взятых элементов, находящихся с ним в $$$1$$$ строке/столбце.

\item Учитывая всё выше сказанное, мы можем, например, перебрать какие-то $$$t$$$ элементов, какие мы уже взяли — и у нас останется взять $$$k-t$$$ элементов — пересчитаем множество кандидатов, и их станет уже $$$C = (2M(k-t)-1)(k-t-1)+1$$$. И дальше мы можем запускаться рекурсивно :)

Чтобы достаточно быстро пересчитывать кандидатов, заметим, что это, очевидно, подмножество кандидатов, которые были у нас на прошлом шаге.

\item Заметим, что, когда мы перебрали какой-то элемент, будто он входит в ответ, и перешли к следующему — можно считать, что предыдущий элемент уже не входит в ответ (иначе мы перебрали бы этот вариант раньше). Поставим соответствующую метку.

А дальше, когда мы уже насчитали следующее множество кандидатов, мы можем просто удалить из него все помеченные элементы. Это делит наше решение на $$$t!$$$, если верить, что элементы переходят в следующее множество кандидатов достаточно равномерно (где $$$t$$$ — число уже взятых элементов), так как из всех их перестановок мы учтём только $$$1$$$. В любом случае, ускоряет :) \end{enumerate}

Теперь пошла уже моя склейка этих идей, по идее, приводящая нас к успеху (если нигде не набагать :)

Будем перебирать по убыванию, начиная с $$$k$$$, максимальное кол-во элементов в $$$1$$$ строке/столбце. Обозначим его на текущем шаге за $$$M$$$ (собственно, это и есть $$$M$$$ по определению). И число кандидатов $$$C$$$ будет уменьшаться с уменьшением $$$M$$$.

Заметим, что тогда соответствующих кандидатов-строк (на линию с $$$M$$$ элементами) будет не больше, чем $$$\min(n, \frac CM)$$$ — ведь в кандидате-строке, очевидно, должно быть минимум $$$M$$$ кандидатов-элементов. И аналогично со столбцами.

Теперь переберём строку/столбец из кандидатов. По нашему предположению в ней ровно $$$M$$$ элементов взято, но тогда из $$$1$$$ пункта для них у нас есть только $$$k$$$ вариантов (а не $$$Mk$$$, как может показаться изначально). Для каждой линии-кандидата, если в ней всего $$$t \leqslant k$$$ элементов кандидатов, мы можем выбрать $$$M$$$ из них $$$C_t^M$$$ способами.

Оставшиеся $$$k-M$$$ элементов выберем в тупую рекурсивно (каждый раз пересчитываем кандидатов и выбираем элемент из них — и с помощью меток оно ещё делится на $$$(k-M)!$$$ примерно).

Если аккуратно посчитать число операций (или потестить решение) — можно понять, что для $$$M \geqslant 3$$$ мы выбираем из остальных $$$\leqslant 3$$$ элемента, и это работает достаточно быстро. Остался случай, когда $$$M \leqslant 2$$$.

Пусть мы уже взяли некоторое множество элементов в ответ. Теперь есть $$$2$$$ варианта — все оставшиеся $$$a_{ij}$$$ в ответе изолированные, или есть хотя бы $$$1$$$ пара в $$$1$$$ строке/столбце.

Если все вершины изолированные — понимаем, что $$$M = 1$$$. То есть, при текущем $$$k$$$ кандидатов $$$C = (2k-1)(k-1)+1$$$ (у нас сейчас $$$k$$$ — кол-во элементов, которые ещё нужно взять в ответ). Также используем метки времени.

Если аккуратно всё посчитать (или опять-таки потестить) — понимаем, что наше рекурсивное решение выше снова работает вполне быстро (даже если изначально все $$$a_{ij}$$$ в ответе изолированные).

Хорошо, а если у нас есть пара вершин в $$$1$$$ строке/столбце — просто запустим наше решение с перебором максимальной по кол-ву элементов в ответе строки рекурсивно :)

Как мы помним, строк-кандидатов $$$\min(n, C/2)$$$ — так как $$$M = 2$$$. И аналогично $$$C = (4k-1)(k-1)+1$$$. Мы выбираем из каждой $$$C_k^2$$$ варианта максимум. Со столбцами аналогично. А затем из $$$k$$$ вычитается $$$2$$$ — глубина не больше $$$3$$$ будет. Короче, в целом, и если посчитать, и если запустить — тоже срабатывает :)

Только важно понимать, что если мы не взяли элемент в кандидаты на пару — он всё ещё может войти в изолированные вершины. Поэтому метки для них должны быть раздельные.

И да, понятное дело, что я опустил ещё некоторые оптимизации, какие-то левые идеи — думаю, из данного базиса фактов можно собрать под сотню разных работающих решений. Хотя на самой олимпиаде, как мы видим, получилось только $$$1$$$ :) Так что, дерзайте!