13904번: 과제

https://www.acmicpc.net/problem/13904


$O(n\lg n)$

과제마감일 순으로 보면서 w1~wi 중 큰 순으로 최대 di개 이외 나머지는 스케줄 상에서 제외한다.

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
int n, res;
priority_queue<int> pq;
pair<int, int> p[1000];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &p[i].first, &p[i].second);
    sort(p, p + n);
    for (int i = 0; i < n; i++) {
        pq.push(-p[i].second);
        res += p[i].second;
        if (pq.size() > p[i].first) res += pq.top(), pq.pop();
    }
    printf("%d", res);
    return 0;
}