Задача с Шада
На дороге в некоторых местах разбросаны золотые монеты. Для каждой монеты известно ее местоположение, которое задается одним целым числом — расстоянием в метрах от начальной отметки. Все монеты расположены правее начальной отметки. Али-баба бегает по дороге и собирает монеты, начиная делать это в момент времени 0. За одну секунду он пробегает ровно один метр. У каждой монеты есть крайний срок, до которого (включительно) ее нужно подобрать, иначе монета исчезнет. Али-баба должен собрать все монеты и сделать это за минимально возможное время. Он может стартовать в любой точке прямой, собирать монеты в произвольном порядке, но обязательно нужно успеть собрать все монеты и при этом минимизировать затраченное время. Если собрать все монеты не получится вывести No solution.
(1 <= n <= 1e3) - количество монет.
Каждая монета определяется двумя числами (xi, ti) - место положение и время за которое нужно взять

Решение:
В задаче вы должны выбрать стартовую позицию от которой начнете движение. Пусть это точка xi тогда ваши движение представляется последовательностью R и L (где R - движение на одну позицию вправо, а L на одну влево).

Решим задачу динамическим программированием.
Давайте отсортируем все монеты по координате в которой они стоят.
Пусть dp[l][r][0] - минимальное количество минут необходимое, чтобы набрать все монеты на позициях с l по r и при этом в конце вы окажитесь в позиции xl, аналогично dp[l][r][1], но уже окажитесь на позиции xr.

Вы можете обновить состояние dp[l - 1][r][0] через dp[l][r][0] или dp[l][r][1] в первом случае у вас должно выполняться условие x[l] - x[l - 1] + dp[l][r][0] <= t[l - 1], а во втором x[r] - x[l - 1] + dp[l][r][1] <= t[l - 1]. Аналогично обновляем и dp[l][r + 1][1].

База дп. Поставим для всех l, r (1 <= l, r <= n) dp[l][r][0] = dp[l][r][1] = INF и после dp[l][l][0] = dp[l][l][1] = 0 так как мы можем сами выбирать с какой позиции нам начинать.

Выводим No solution если dp[1][n][0] = dp[1][n][1] = INF, иначе выводим min(dp[1][n][0], dp[1][n][1])
Время работы O(n^2)