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

Есеп A. Жұмыс па әлде демалыс па?

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

1.5 seconds

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

256 megabytes

Адиде $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

легчайшая