Submission #440585

#	Time	Username	Problem	Language	Result	Execution time	Memory
440585		nikolapesic2802	Schools (IZhO13_school)	C++14	100 / 100	383 ms	36476 KiB

school

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define dec(x, y) fixed << setprecision((y)) << (x)
#define xx first
#define yy second
#define srt(v) sort((v).begin(), (v).end())
#define srtr(v) sort((v).rbegin(), (v).rend())
#define pb push_back
#define popb pop_back
#define sz(a) (int)(a).size()
#define len(a) (int)(a).length()
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int n, m, s;
pll x[300010];
set<pll> naja, najb, raz;
ll rez;
int main() {
    ios;
    cin >> n >> m >> s;
    for(int i=0; i<n; ++i) {
        cin >> x[i].xx >> x[i].yy;
    }
    sort(x, x+n, greater<pll>());
    for(int i=0; i<m; ++i) {
        rez+=x[i].xx;
        raz.insert({x[i].yy-x[i].xx, (ll)i});
    }
    for(int i=m; i<n; ++i) {
        naja.insert({x[i].xx, (ll)i});
        najb.insert({x[i].yy, (ll)i});
    }
    for(int kk=0;kk<s;kk++){
    	
        bool uzeo1=0, uzeo2=0;
        pll pr, dr, tr;
        if(!najb.empty()) {
            pr=*prev(najb.end());
            uzeo1=1;
        }
        if(!raz.empty() && !naja.empty()) {
            dr=*prev(raz.end());
            tr=*prev(naja.end());
            uzeo2=1;
        }
        if(!uzeo2) {
            rez+=pr.xx;
            najb.erase(prev(najb.end()));
            naja.erase({x[pr.yy].xx, pr.yy});
        }
        else if(!uzeo1) {
            rez+=dr.xx+tr.xx;
            if(!raz.empty()) raz.erase(prev(raz.end()));
            if(!naja.empty()) naja.erase(prev(naja.end()));
            najb.erase({x[tr.yy].yy,tr.yy});
            raz.insert({x[tr.yy].yy-x[tr.yy].xx, tr.yy});
        }
        else if(pr.xx>dr.xx+tr.xx) {
            rez+=pr.xx;
            if(!najb.empty()) najb.erase(prev(najb.end()));
            auto it=naja.find({x[pr.yy].xx, pr.yy});
            if(it!=naja.end() && !naja.empty()) naja.erase(it);
        }
        else{
            rez+=dr.xx+tr.xx;
            if(!raz.empty()) raz.erase(prev(raz.end()));
            if(!naja.empty()) naja.erase(prev(naja.end()));
            najb.erase({x[tr.yy].yy,tr.yy});
            raz.insert({x[tr.yy].yy-x[tr.yy].xx, tr.yy});
        }
    }
    cout << rez;
    return 0;
}

• Subtask 1: 100 / 100