Submission #46875564

---

Source Code Expand

#include <bits/stdc++.h>

void solve(std::istream& is, std::ostream& os) {
    using Num = long long int;
    Num n {0};
    is >> n;

    std::vector<std::pair<Num, Num>> items(n);
    for(auto&& [t, d] : items) {
        is >> t >> d;
        d += t;
    }
    std::sort(items.begin(), items.end());

    std::priority_queue<Num, std::vector<Num>, std::greater<Num>> q;
    Num answer {0};
    Num index {0};
    Num t = items.begin()->first;
    while((index < n) || !q.empty()) {
        while(index < n) {
            const auto item = items.at(index);
            if (item.first <= t) {
                q.push(item.second);
                ++index;
            } else {
                break;
            }
        }

        if (!q.empty()) {
            const auto d = q.top();
            q.pop();
            if (d >= t) {
                ++answer;
                ++t;
            }
        }

        if (q.empty() && (index < n)) {
            t = std::max(t, items.at(index).first);
        }
    }

    os << answer << "\n";
    return;
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Judge Result