[백준 c++] 1202 보석 도둑

문제 설명

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.
상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.
상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)
다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)
다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)
모든 숫자는 양의 정수이다.

출력
첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

풀이

주어진 시간이 1초라서 단순히 각각 30만개의 인풋을 이중for문으로 풀면 시간초과가 난다.
가격이 최대가 되어야하니까 가격 기준으로 내림차순 정렬, 가방은 오름차순 정렬로 풀어봤는데 풀이도 복잡했고 메모리 초과가 났다..

가방과 보석(무게기준) 모두 오름차순 정렬하고 각 가방이 넣을 수 있는 보석의 가격을 다 priority_queue(내림차순 정렬)에 넣는다. 그러면 pq.top()은 해당 가방이 담을 수 있는 보석의 최대 가격이 된다.
앞의 가방에서 넣을 수 있는 보석은 뒤의 가방도 넣을 수 있다.
pop을 한 후에 pq에는 이전에 채택되지 않은 보석의 가격도 계속 남아있으면서 계속 내림차순으로 정렬되기 때문에 가방들은 항상 가장 큰 최선의 보석을 담을 수 있게 된다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, k, m, v;
long long res, c;
vector<pair<int, int>> jew;
vector<int> bag;
priority_queue<int, vector<int>, less<int>> pq;
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> m >> v;
        jew.push_back({m, v});
    }
    for (int i = 0; i < k; i++)
    {
        cin >> c;
        bag.push_back(c);
    }
    sort(jew.begin(), jew.end());
    sort(bag.begin(), bag.end());

    int j = 0;
    for (int i = 0; i < k; i++)
    {
        while (j < n && bag[i] >= jew[j].first)
        {
            pq.push(jew[j].second);
            j++;
        }
        if (!pq.empty())
        {
            res += pq.top();
            pq.pop();
        }
    }
    cout << res << "\n";
}