## Hướng dẫn:
**Nhận xét:** Con đường hái hoa tối ưu nhất của Marisa là hái những bông hoa ở những vị trí theo thứ tự tăng dần, có nghĩa là nếu Marisa hái bông hoa ở vị trí *x* thì bông hoa tiếp theo Marisa có thể hái phải là *y* với *y* > *x*.
**Giả sử:** Marisa hái bông hoa ở vị trí *x*
- Nếu Marisa hái bông hoa *y* (*y* < *x*) thì phải mất thêm chi phí đi từ *x* về *y* cộng với thời gian hái hoa ở *y*.
- Trong khi đó Marisa bắt đầu từ vị trí *0* đi đến *x* thì trên đường đi Marisa có thể dừng lại hái hoa ở *y* xong rồi mới đi đến hái hoa ở *x*.
Rõ ràng Marisa hái hoa ở vị trí *x* rồi hái hoa ở vị trí *y* (*y* > *x*) là phương pháp tối ưu nhất.
Code:
```
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=a; i<=b; ++i)
template<class X, class Y>
bool maximize(X &x, const Y &y){return (x < y) ? x = y, 1 : 0;}
#define ii pair<int,int>
const int MAXN = 1e6 + 5;
priority_queue<int> pq;
int n,m;
ii a[MAXN];
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
FOR(i,1,n) cin >> a[i].first >> a[i].second;
sort(a+1,a+n+1);
int res = 0;
int cur = 0;
FOR(i,1,n)
{
pq.push(a[i].second);
cur += a[i].second;
while (pq.size() && cur + a[i].first > m)
{
cur -= pq.top();
pq.pop();
}
maximize(res,pq.size());
}
cout << res;
return 0;
}
```
hungkm466
Created at
1 likes