Submission #897089

#TimeUsernameProblemLanguageResultExecution timeMemory
897089borisAngelovSchools (IZhO13_school)C++17
100 / 100
270 ms31368 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 300005; int n, music, sport; pair<int, int> a[maxn]; multiset<pair<int, pair<int, int>>, greater<pair<int, pair<int, int>>>> currentMusic; multiset<pair<int, int>, greater<pair<int, int>>> otherByMusic; multiset<pair<int, int>, greater<pair<int, int>>> otherBySport; void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); cin >> n >> music >> sport; for (int i = 1; i <= n; ++i) { cin >> a[i].first >> a[i].second; } sort(a + 1, a + n + 1, greater<pair<int, int>>()); long long ans = 0; for (int i = 1; i <= music; ++i) { ans += a[i].first; currentMusic.insert({a[i].second - a[i].first, {a[i].first, a[i].second}}); } for (int i = music + 1; i <= n; ++i) { otherByMusic.insert({a[i].first, a[i].second}); otherBySport.insert({a[i].second, a[i].first}); } for (int steps = 1; steps <= sport; ++steps) { long long case1 = 0, case2 = 0; //long long case1 = (*otherBySport.begin()); //long long case2 = (*currentMusic.begin()) + (*otherByMusic.begin()); pair<int, int> currSport = (*otherBySport.begin()); case1 = currSport.first; pair<int, pair<int, int>> currMus = (*currentMusic.begin()); pair<int, int> otherMus = (*otherByMusic.begin()); case2 = currMus.first + otherMus.first; if (case1 >= case2) { ans += case1; auto it = otherBySport.begin(); int x = it -> first; int y = it -> second; otherBySport.erase(otherBySport.find({x, y})); otherByMusic.erase(otherByMusic.find({y, x})); } else { ans += case2; auto it = currentMusic.begin(); pair<int, pair<int, int>> curr = *it; currentMusic.erase(currentMusic.find(curr)); pair<int, int> currMusic = (*otherByMusic.begin()); otherByMusic.erase(otherByMusic.find(currMusic)); otherBySport.erase(otherBySport.find({currMusic.second, currMusic.first})); currentMusic.insert({currMusic.second - currMusic.first, currMusic}); } } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...