Submission #204529

#	Time	Username	Problem	Language	Result	Execution time	Memory
204529		Saboon	Hotel (CEOI11_hot)	C++14	100 / 100	1315 ms	46392 KiB

hot

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e6 + 10;

pair<int,int> offer[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	int n, m, o;
	cin >> n >> m >> o;
	multiset<pair<int,int> > room;
	for (int i = 0; i < n; i++){
		int p, c;
		cin >> p >> c;
		room.insert({c, p});
	}
	for (int i = 0; i < m; i++){
		int v, d;
		cin >> v >> d;
		offer[i] = {v, d};
	}
	sort(offer, offer + m);
	reverse(offer, offer + m);
	vector<int> vals;
	for (int i = 0; i < m; i++){
		auto it = room.lower_bound({offer[i].second, 0});
		if (it == room.end())
			continue;
		vals.push_back(offer[i].first - it->second);
		room.erase(it);
	}
	sort(vals.rbegin(), vals.rend());
	ll sum = 0;
	for (int i = 0; i < min((int)vals.size(), o); i++)
		sum += max(0, vals[i]);
	cout << sum << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10