Submission #348813

#TimeUsernameProblemLanguageResultExecution timeMemory
348813nicolaalexandraSchools (IZhO13_school)C++14
100 / 100
382 ms13548 KiB
#include <bits/stdc++.h>
#define DIM 300010
using namespace std;

pair <int,int> v[DIM];
int a[DIM],b[DIM];
long long pref[DIM],suf[DIM];
multiset <int> s;
int n,nra,nrb,i;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>nra>>nrb;
    for (i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        v[i] = make_pair(b[i]-a[i],i);
    }

    sort (v+1,v+n+1);

    long long sum = 0;
    for (i=1;i<=nra;i++){
        sum += a[v[i].second];
        s.insert(a[v[i].second]);
    }

    pref[nra] = sum;
    for (i=nra+1;i<=n;i++){
        sum += a[v[i].second];

        s.insert(a[v[i].second]);

        /// scad minimul din set
        sum -= *s.begin();
        s.erase(s.begin());

        pref[i] = sum;
    }


    sum = 0;
    s.clear();
    for (i=n-nrb+1;i<=n;i++){
        sum += b[v[i].second];
        s.insert(b[v[i].second]);
    }

    suf[n-nrb+1] = sum;

    for (i=n-nrb;i;i--){
        sum += b[v[i].second];
        s.insert(b[v[i].second]);

        sum -= *s.begin();
        s.erase(s.begin());

        suf[i] = sum;
    }

    long long sol = 0;
    for (i=0;i<=n;i++)
        sol = max (sol,pref[i] + suf[i+1]);
    cout<<sol;


    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...