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

Можно перебрать a b, что a^2+b^2=d. Теперь найти кол-во пар i j, что x[i]+a=x[j] и y[i]+b=y[j]. Это делается дихом.

Всегда существует оптимальное решение следующего вида — разобьем всю последовательность на отрезочки и сначала заберем все числа из первого отрезочка (внутри отрезочка берем числа в обратном порядке), потом из второго отрезочка и так далее. К примеру, если мы разбили последовательность на отрезки вот так: [a₁ a₂ a₃][a₄ a₅][a₆ a₇ a₈ a₉], то забирать числа будем в порядке a₃, a₂, a₁, a₅, a₄, a₉, a₈, a₇, a₆. Доказывать это сейчас не буду.

Дальше получается довольно простое ДП: f(k) -  максимальная сумма, которую можно получить убрав префикс длины k. Переход будет такой:

f(k) = f(k - 1) + a_k + 1, если последний отрезочек будет длины 1;

, если последний отрезочек — [j, k].

Замечаем, что второй переход можно записать вот так:

, где S — префиксные суммы и получаем константный переход.

Решение: Бинарный поиск по ответу.

Сначала очень просто можно узнать, какое максимальное число вхождений у нас может быть.

Просто возьмем и посчитаем, какое максимальное кол-во вхождений какой-нибудь буквы мы имеем. Назовем это кол-во вхождений need.

Давайте научимся проверять какую-нибудь длину len. Проверять длину len — значит узнать, есть ли у нас такая подстрока длины len, что она имеет need непересекающихся вхождений.

Это можно делать за используя полиноминальные хэши. Посчитаем хэш всех подстрок длины len. Выпишем такие пары (hash, position) — хэш подстроки и позиция подстроки. Теперь давайте для каждого уникального hash выпишем все его position в возрастающем порядке. Теперь, зная все position для фиксированного hash не составляет труда посчитать максимальную подпоследовательность из этих позиций, что разница между соседними элементами подпоследовательности больше либо равна len (это условие нужно, потому что мы ищем непересекающиеся вхождения). Это можно легко подсчитать используя ДП:

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

Теперь можно просто считать следующее ДП:

f_i — максимальная длина подпоследовательности из префикса a длины i. Понятно, что f₀ = 0

Подсчет данного ДП ведется так:

f_i = max(f_j, f₀) + 1, где j — такая максимальная позиция, что a_i - a_j ≥ len. Если такой позиции нет, то j = 0. Найти такое j можно бинарным поиском.

Как говорилось выше: давайте для каждого уникального hash выпишем все его позиции и запустим на них вышеописанное ДП. И возьмем максимум среди всех результатов запуска ДП. Это и будет максимальное кол-во непересекающихся вхождений строки, имеющей длину len. Теперь легко проверить подходит длина len или нет.

Также надо заметить, что если подходит длина len, то и длина len - 1 тоже подходит, значит можно использовать бинарный поиск, чтобы найти максимальное len, которое подходит.

Итоговая асимптотика решения:

Для лучшего понимания выкладываю код.