#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 300005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
ll n, m, s, cbm[MAXN], cbs[MAXN], r = 0;
pair<ll, ll> c[MAXN];
bool cmp_cbm(const ll& a, const ll& b){
if(c[a].first == c[b].first) return c[b].second > c[a].second;
return c[a].first < c[b].first;
}
bool cmp_cbs(const ll& a, const ll& b){
if(c[a].second == c[b].second) return c[b].first > c[a].first;
return c[a].second < c[b].second;
}
set<pair<ll, ll>> m_o, m_n, s_o, s_n;
set<pair<pair<ll, ll>, ll>> cm, um;
set<pair<pair<ll, ll>, ll>> cs, us; // add additional -> if tie, sort by second
int main(){
cin >> n >> m >> s;
FOR(i, 1, n){
cbm[i] = cbs[i] = i;
cin >> c[i].first >> c[i].second;
}
sort(cbm + 1, cbm + 1 + n, cmp_cbm);
sort(cbs + 1, cbs + 1 + n, cmp_cbs);
FOR(i, 1, n){
// add to music
if(n - s + 1 <= i && i <= n){
m_o.insert({c[cbs[i]].first - c[cbs[i]].second, cbs[i]});
cs.insert({{c[cbs[i]].second, -c[cbs[i]].first}, cbs[i]});
}else{
m_n.insert({c[cbs[i]].first, cbs[i]});
us.insert({{c[cbs[i]].second, -c[cbs[i]].first}, cbs[i]});
}
// add to sporcbs
if(n - m + 1 <= i && i <= n){
s_o.insert({c[cbm[i]].second - c[cbm[i]].first, cbm[i]});
cm.insert({{c[cbm[i]].first, -c[cbm[i]].second}, cbm[i]});
}else{
s_n.insert({c[cbm[i]].second, cbm[i]});
um.insert({{c[cbm[i]].first, -c[cbm[i]].second}, cbs[i]});
}
}
while(m + s > 0){
pair<ll, ll> b = {LLONG_MIN, LLONG_MIN};
if(m && !m_o.empty()) b = max(b, {(*m_o.rbegin()).first + c[(*us.rbegin()).second].second, c[(*m_o.rbegin()).second].first});
if(m && !m_n.empty()) b = max(b, {(*m_n.rbegin()).first, (*m_n.rbegin()).first});
if(s && !s_o.empty()) b = max(b, {(*s_o.rbegin()).first + c[(*um.rbegin()).second].first, c[(*s_o.rbegin()).second].second});
if(s && !s_n.empty()) b = max(b, {(*s_n.rbegin()).first, (*s_n.rbegin()).first});
// choose music sch thacbs a top sporcbs sch too
ll ci;
bool ti = false;
if(!m_o.empty() && b == make_pair((*m_o.rbegin()).first + c[(*us.rbegin()).second].second, c[(*m_o.rbegin()).second].first)){
ci = (*m_o.rbegin()).second; m_o.erase(*m_o.rbegin()), ti = true;
}else if(!m_n.empty() && b == make_pair((*m_n.rbegin()).first, (*m_n.rbegin()).first) ){
ci = (*m_n.rbegin()).second; m_n.erase(*m_n.rbegin()), ti = true;
}else if(!s_o.empty() && b == make_pair((*s_o.rbegin()).first + c[(*um.rbegin()).second].first, c[(*s_o.rbegin()).second].second)){
ci = (*s_o.rbegin()).second; s_o.erase(*s_o.rbegin());
}else{
ci = (*s_n.rbegin()).second; s_n.erase(*s_n.rbegin());
}
if(ti){
r += c[ci].first, m--;
}else{
r += c[ci].second, s--;
}
if(cm.find({{c[ci].first, -c[ci].second}, ci}) != cm.end()){
cm.erase({{c[ci].first, -c[ci].second}, ci});
s_o.erase({c[ci].second - c[ci].first, ci});
}else{
um.erase({{c[ci].first, -c[ci].second}, ci});
s_n.erase({c[ci].second, ci});
if(!cm.empty()){
ll ci2 = (*cm.begin()).second; pair<ll, ll> civ = (*cm.begin()).first;
cm.erase(cm.begin()), um.insert({civ, ci2});
s_o.erase({c[ci2].second - c[ci2].first, ci2});
s_n.insert({c[ci2].second, ci2});
}
}
if(cs.find({{c[ci].second, -c[ci].first}, ci}) != cs.end()){
cs.erase({{c[ci].second, -c[ci].first}, ci});
m_o.erase({c[ci].first - c[ci].second, ci});
}else{
us.erase({{c[ci].second, -c[ci].first}, ci});
m_n.erase({c[ci].first, ci});
if(!cs.empty()){
ll ci2 = (*cs.begin()).second; pair<ll, ll> civ = (*cs.begin()).first;
cs.erase(cs.begin()), us.insert({civ, ci2});
m_o.erase({c[ci2].first - c[ci2].second, ci2});
m_n.insert({c[ci2].first, ci2});
}
}
}
cout << r << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Correct |
0 ms |
372 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Incorrect |
6 ms |
1736 KB |
Output isn't correct |
| 8 |
Incorrect |
7 ms |
1628 KB |
Output isn't correct |
| 9 |
Incorrect |
9 ms |
1884 KB |
Output isn't correct |
| 10 |
Incorrect |
7 ms |
1704 KB |
Output isn't correct |
| 11 |
Incorrect |
8 ms |
1884 KB |
Output isn't correct |
| 12 |
Incorrect |
8 ms |
1884 KB |
Output isn't correct |
| 13 |
Incorrect |
76 ms |
11084 KB |
Output isn't correct |
| 14 |
Incorrect |
157 ms |
23120 KB |
Output isn't correct |
| 15 |
Incorrect |
344 ms |
46676 KB |
Output isn't correct |
| 16 |
Incorrect |
653 ms |
52820 KB |
Output isn't correct |
| 17 |
Incorrect |
727 ms |
64548 KB |
Output isn't correct |
| 18 |
Incorrect |
775 ms |
70740 KB |
Output isn't correct |
| 19 |
Incorrect |
869 ms |
76372 KB |
Output isn't correct |
| 20 |
Incorrect |
1006 ms |
87896 KB |
Output isn't correct |
