Submission #1092991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092991		codexistent	Schools (IZhO13_school)	C++14	20 / 100	1006 ms	87896 KiB

school

#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;
}

• Subtask 1: 20 / 100