Задача с контеста Яндекс.

Решение:
Во первых заметим, что x[i] <= x[i + 1]. Задача сводится к тому, чтобы выбрать индексы i_1, i_2, ..., i_k, таким образом, что t[i_1] + t[i_2] + .... + t[i_k] + x[i_k] <= T, а также k-> max.

По факту, если бы мы знали до какой позиции Андрею нужно дойти (то есть i_k) то нам нужно было бы взять t[i_k] + x[i_k] и взять самые маленькие t слева от позиции i_k, таким образом чтобы сумма была <=T. Так как мы не знаем оптимальную позицию i_k то куда Андрею стоит идти, нам придется ее перебирать.

Давайте идти слева направо по позициям (то есть for i in range(n)) и предположим, что у вас есть оптимальный набор t-шок слева, я буду хранить их в multiset, (на питоне можно heap).
Пусть сумма оптимальных t-шок (чисел которые лежат в multiset) равна sum_T.
Тогда логично, когда вы в i-той позиции убирать из multiset максимальные числа до тех пор пока sum_T + x[i] > T (так как x[i] возрастают и нам незачем таскать за собой в следующие позиции ненужные t-щки).
Теперь мы оставили такой набор t-щик (замечу мы сделали не хуже для следующих позиций).
У нас 3 случая:
1) sum_T + t[i] + x[i] <= T
2) sum_T + t[i] <= T
3) максимальная t-щка в оптимальном набор больше чем t[i]
Рассмотрим все эти три случая по порядку и обновим ответ/оптимальный набор. (Подробнее смотрите код)

Время работы алгоритма O(NlogN).

Код и полное условие в комментариях.