1202번: 보석 도둑

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


$O(n\lg n+k\lg {nk})$

큰 가방은 작은 가방이 넣을 수 있는 보석은 모두 넣을 수 있기 때문에 작은 가방부터 넣을 수 있는 최대 가치의 보석을 넣으면 된다.

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int MAX_N = 3e5;
typedef long long ll;
int n, k, c[MAX_N];
ll r;
pair<int, int> p[MAX_N];
priority_queue<int> pq;
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d %d", &p[i].first, &p[i].second);
    for (int i = 0; i < k; i++) scanf("%d", c + i);
    sort(p, p + n);
    sort(c, c + k);
    for (int i = 0, j = 0; i < k; i++) {
        while (j < n && p[j].first <= c[i]) pq.push(p[j++].second);
        if (!pq.empty()) {
            r += pq.top();
            pq.pop();
        }
    }
    printf("%lld", r);
    return 0;
}