思路与算法

每个任务耗时恰为1，选择若干任务后，按截止时间升序执行即可检查是否能安排。将所有任务按截止时刻排序，用小根堆保存目前选择的奖励，总和sum同步维护。

处理截止时间为t、奖励w的任务时，先把w入堆；若堆大小超过t，说明在时刻t之前放不下这些任务，删除堆内最小奖励。遍历完成后输出sum。截止时间相同也按同样过程处理，不需要专门分组。

正确性说明

按截止时间升序处理。此前堆内任务按截止升序可执行。加入截止为t的新任务后，若堆大小不超过t，可把新任务放在最后；否则此前堆大小必为t，新集合大小为t+1。删除其中任何一个任务后，原有较早截止限制不会增加，且总数回到t，因此仍可行。

证明更强的不变量：对任意不超过堆大小的q，堆中最大的q个奖励之和，等于已处理任务中可行的q任务集合的最大奖励。初始空堆成立。加入新任务w时，一个q任务最优方案若不包含新任务，奖励不超过旧堆最大的q项；若包含新任务，其余q-1项奖励不超过旧堆最大的q-1项。反过来，这q-1项可行，且q<=t时可以把新任务接到最后。因此两种上界的最大值，恰好是旧堆加w后最大的q项，且可达到。

若发生超容量，只删整个集合的最小奖励，所有q<=t的最大q项均未改变；而全部已处理任务截止都不超过t，不存在超过t项的可行集合。因此不变量继续成立。若没有超容量，新堆本身可行，其任意子集也可行，同样满足不变量。奖励均为正数，最优解可以取到最大可行任务数，即当前堆大小；遍历结束时sum就是最大奖励。

复杂度

存储并读取N对任务、初始化数组O(N)，排序O(N log N)，每个任务至多入堆一次、出堆一次，堆操作O(N log N)。总时间O(N log N)，额外空间O(N)。总奖励最大200000乘2000=400000000，程序用long long累加。

易错点

1. 截止时刻t表示第t个单位时间结束前完成，最多可安排t个单位任务，不是t-1。
2. 必须先按截止时间排序；堆顶保留可淘汰的最小奖励。
3. 截止时间可能比任务总数大，不应以截止值大小分配数组；当前堆方案不依赖时间上界分配。
4. 本题输入每行一对截止时间和奖励、N上限200000；与GESP巧夺大奖的两个数组输入及500规模分开保留。
5. 覆盖同一截止全部竞争、全部可安排、奖励相同、最大N及第二组公开样例。

参考代码（C++11）

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n))
        return 0;
    vector<pair<int, int>> a(n);
    for (auto &x : a)
        cin >> x.first >> x.second;
    sort(a.begin(), a.end());
    priority_queue<int, vector<int>, greater<int>> q;
    long long sum = 0;
    for (auto x : a) {
        q.push(x.second);
        sum += x.second;
        if ((int)q.size() > x.first) {
            sum -= q.top();
            q.pop();
        }
    }
    cout << sum << '\n';
}