3-й этап Республиканской олимпиады по информатике 2021-2022, 2 тура

Задача A. Работать или отдыхать?

Ограничение по времени:

1.5 секунд

Ограничение по памяти:

256 мегабайт

У Ади есть $S$ тенге. В каждый из следующих $N$ дней он решил, что будет либо целый день работать, либо целый день отдыхать. Он высчитал, что если будет работать в $i$-й день, то заработает $a_i$ тенге. А чтобы отдохнуть в $i$-й день, он потратит $b_i$ тенге. Другими словами, если в $i$-й день он будет работать, то количество его денег увеличиться на $a_i$, а если будет отдыхать, то количество денег уменьшится на $b_i$. Какое максимальное количество дней он может отдохнуть? При этом, ни в какой момент времени количество его денег не должно быть отрицательным.

Формат входного файла

В первой строке находятся два целых числа $N$ и $S$($1 <= N <= 200000$, $0 <= S <= 10^9$) — количество дней и изначальное количество денег. В следующих $N$ строках находятся по два целых числа $a_i$ и $b_i(0 <= a_i,b_i <= 10^9)$.

Формат выходного файла

Выведите одно целое число — максимальное количество дней, в которые Ади может отдохнуть.

Примеры:

Вход

3 5
1 4
1 3
2 3

Ответ

2

Вход

5 12
0 5
0 4
0 7
0 4
0 4

Ответ

3

Замечание

В первом примере: в первый день он будет работать, а второй и третий день отдыхать. Во втором примере: он будет отдыхать в дни $2$, $4$ и $5$. ( Temirlan Satylkhanov )

Комментарий/решение

Как я понял это задача о ранце с динамической грузоподъемностью, если нет пожалуйста можете дать подсказку

показать/скрыть код

n, s = map(int, input().split())
data = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: (x[1], x[0]))

days = 0
for earn, waste in data:
    if s <= 0:
        s += earn
    else:
        s -= waste
        days += 1

print(days)

C++

Copy

легчайшая