С-шка решается жадно. Пусть для определенности мы в начале всегда идем вправо. Для каждой точки можно вывести довольно несложную формулу с четырьмя случаями для времени, когда мы её посетим. Заметим, что мы постепенно посещаем все точки с максимумом модулей разностей координат до начальной 1,2,3... Чем меньше максимум этих значений тем лучше. Поэтому бинпоиском найдём минимальное D, проверяя за O(N), что множество точек, где может располагаться старт не пусто и не занято контрольными точками. Это множество точек — пересечение квадратов с центрами в контрольных точках и сторонами 2D+1 x 2D+1.

Теперь множество точек, где может располагаться центр образует границу некоторого прямоугольника. Внутренность пустая, т.к. точки там имеют меньшее D. Можно разбирать какие-то случаи, но понятно, что нас интересуют или углы или самые левые, правые, нижние или верхние точки на границах. Найдём эти точки и попытаемся улучшить ответ.

Повернём все точки на 90 градусов и повторим еще 3 раза.

В F заходит куб: построим полный граф на всех концах барьеров (это не совсем очевидно из условия, но они не пересекаются и не касаются, что сильно упрощает жизнь), начальной и конечной точках, в котором стоимость ребра из одной точки в другую равна времени, которое нужно, чтобы пройти из первой точки во вторую по прямой (понятно, что в минимальном ответе для любого маленького участка, не являющегося отрезком не должно быть возможности срезать по прямой, то есть любой такой маленький участок должен как-то обходить какой-то барьер, в то время, как прямая должна его пересекать; из этого уже можно аккуратно вывести, что оптимальный ответ ходит между вершинами нашего графа по прямой).

Если мы построим такой граф, то дальше надо просто запустить Дейкстру за квадрат. Чтобы построить граф, просто переберём все пары точек и посчитаем, сколько барьеров пересечёт отрезок между ними с одной важной оптимизацией: когда мы перебираем пару точек (x₁, y₁) и (x₂, y₂), то нужно учитывать вертикальные барьеры только с x от min(x₁, x₂) + 1 до max(x₁, x₂) - 1 и горизонтальные барьеры с y только с min(y₁, y₂) + 1 до max(y₁, y₂) - 1, так как другие барьеры отрезок заведомо не пересечёт (выделить их можно с помощью бинпоиска в отсортированных массивах горизонтальных и вертикальных отрезков).

UPD. В ответ на вопрос zeliboba. Почему работает быстрее тупого куба: у нас всего 2n + 2 = 1002 (назовём это число m) x-ов (с повторениями), столько же y-ов. Тогда если просуммировать для каждой пары x-ов сколько между ними других x-ов, то получим Мы рассмотрим горизонтальные барьеры суммарно не больше, чем столько раз, аналогично с вертикальными. проверок на пересечение отрезков для m = 1002 уже звучит вменяемо. На самом деле понятно, что это грубоватая оценка сверху, так как у нас всего n = 500 барьеров суммарно.

Я сдал рекурсию с запоминанием. Главное было влезть в ограничение по памяти.

1) Пусть t₀ ≥ ... ≥ t_2n - 2. Возьмем нулевой элемент. Теперь по t будет все хорошо, если взять любого из (t₁ и t₂), из (t₃ и t₄) и т. д., так как t₀ мажорирует любого из t₁ и t₂, любой из t₁ и t₂ мажорирует любого из t₃ и t₄ и т. д. Теперь в каждой паре (b₁, b₂), (b₃, b₄), ... будем выбирать максимум.

Наверное, в С задумывался квадрат — если записывать строчку в виде набора атомарных кусков, то таких кусков будет О(M) (каждое "вырезать и перевернуть" добавляет не более двух кусков), и можно делать одну операцию наивно за О(M) — переставляя куски и меняя им флаги реверса; получим O(M²) суммарно.

Кстати, не в тему — я не заценил идею не писать явно ограничения. Я к тому, что если дать один тест размера 2.5е6, то в той же В у меня пачка векторов свалится по МЛ.

Upd. А что там в С, нормально NM заходит? :D