oj.uz

Submission #597191

# Submission time Handle Problem Language Result Execution time Memory
597191 2022-07-15T17:07:28 Z Trisanu_Das Hotel (CEOI11_hot) C++17
100 / 100
 1036 ms 62880 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
 
#define ll long long
#define vll vector<long long>
#define pll pair<long long, long long>
#define sz(x) int(x.size())
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, m, o; cin >> n >> m >> o;
	multiset<pll> rooms;
	for(int i = 1; i <= n; i++){
		ll c, p;
		cin >> c >> p;
		rooms.insert({p, c});
	}
	vector<pll> offers(m);
	for(int j = 0; j < m; j++)cin >> offers[j].second >> offers[j].first;
	sort(offers.begin(), offers.end(), [] (pll U, pll V){return U.second > V.second;});
	ll res = 0;
	vector<ll> options;
	for(pll z : offers){
		ll capreq = z.first;
		ll gain = z.second;
		auto f = rooms.lower_bound({capreq, -1});
		if(f == rooms.end()) continue;
		if(gain > f->second) options.push_back(gain - f->second);
		rooms.erase(f);
	}
	sort(options.begin(), options.end());
	for(int i = sz(options)-1; i >= 0 && i >= sz(options)-o; i--)
		res += options[i];
	cout << res << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 240 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 992 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3792 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 6348 KB Output is correct
2 Correct 65 ms 7348 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 18212 KB Output is correct
2 Correct 124 ms 13920 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 35864 KB Output is correct
2 Correct 777 ms 47012 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 43688 KB Output is correct
2 Correct 814 ms 62880 KB Output is correct
3 Correct 1036 ms 60052 KB Output is correct