Từ 2025 - Lớp 8.1 (tối thứ 3), 2026 - Thuật toán nâng cao (thầy Hoàng - chiều thứ 7)

Thông tin

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

struct Project {
    long long a, b;
    bool operator<(const Project& other) const {
        return a < other.a;
    }
} p[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long s;
    cin >> n >> s;

    for (int i = 0; i < n; ++i) {
        cin >> p[i].a >> p[i].b;
    }

    sort(p, p + n);

    priority_queue&lt;long long> max_cost;
    long long current_capital = s;

    for (int i = 0; i < n; ++i) {
        if (current_capital >= p[i].a) {
            max_cost.push(p[i].a);
            current_capital += (p[i].b - p[i].a);
        } else if (!max_cost.empty() && max_cost.top() > p[i].a) {
            current_capital -= (p[i].b - p[i].a);
            current_capital += max_cost.top();
            max_cost.pop();
            max_cost.push(p[i].a);
        }
    }

    cout << max_cost.size() << "\n";

    return 0;
}

Huy hiệu