[BOJ] 보석 도둑

[BOJ] 보석 도둑

Problem URL : 보석 도둑

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<pair<int, int>> gem;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int gemNum, bagNum;
	cin >> gemNum >> bagNum;
	for (int i = 0; i < gemNum; i++) {
		int weight, value;
		cin >> weight >> value;
		gem.push_back({ weight, value });
	}
	vector<int> bag;
	for (int i = 0; i < bagNum; i++) {
		int weight;
		cin >> weight;
		bag.push_back(weight);
	}
	sort(gem.begin(), gem.end());
	sort(bag.begin(), bag.end());

	long long sum = 0; [1]
	priority_queue<int> pq;
	for (int i = 0, j = 0; i < bagNum; i++) {
		while (j < gemNum && gem[j].first <= bag[i]) {
			pq.push(gem[j++].second);
		}
		if (!pq.empty()) {
			sum += pq.top();
			pq.pop();
		}
	}
	cout << sum << "\n";

	return 0;
}

Comments

[1] long long이 아닌 int로 하면 범위가 넘어가서 틀리게 된다. 주의하자.