Submission #682690

#	Time	Username	Problem	Language	Result	Execution time	Memory
682690		Ronin13	Schools (IZhO13_school)	C++14	20 / 100	86 ms	6160 KiB

school

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax =1e5 + 1;
const ll linf = 1e18 + 1;
 
multiset <pll> a, b;
multiset <pll, greater<pll> >  c, d;
ll sum = 0;
ll A[nmax], B[nmax];
 
void erase1(){
    int x = a.begin()->s;
    c.erase({B[x] - A[x], x});
    a.erase(a.begin());
}
 
void erase2(){
    int x = b.begin()->s;
    d.erase({A[x] - B[x], x});
    b.erase(b.begin());
}
 
 
 
int main(){
  
    int n; cin >> n;
    int m; cin >> m;
    int s; cin >> s;
    for(int i = 1; i <= n; i++)
        cin >> A[i] >> B[i];
    ll sum = 0;
    vector <pll> vec;
    for(int i= 1; i <= s + m; i++){
        sum += A[i];
        vec.pb({B[i] - A[i], i});
    }
    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    for(int i = 0; i < s; i++){
        int x = vec[i].s;
        b.insert({B[x], x});
        d.insert({A[x] - B[x], x});
        sum += B[x] - A[x];
    }
    for(int i = s; i < s + m; i++){
        int x = vec[i].s;
        a.insert({A[x], x});
        c.insert({B[x] - A[x], x});
    }
    for(int i = s + m + 1; i <= n; ++i){
        ll val1 = 0;
        val1 = sum + A[i];
        if(c.empty() || b.empty()) val1= -linf;
        else val1 += c.begin()->f - b.begin()->f;
        ll val2 = sum + A[i];
        if(a.empty()) val2 = -linf;
        else val2 -= a.begin()->f;
        ll val3 = 0;
        val3 = sum + B[i];
        if(d.empty() || a.empty()) val3 = -linf;
        else val3 += d.begin()->f - a.begin()->f;
        ll val4 = sum + B[i];
        if(b.empty()) val4= -linf;
        else val4 -= b.begin()->f;
        ll mx = max({val1, val2, val3, val4, sum});
        if(mx == sum) continue;
        if(mx == val1){
            erase2();
            int x = c.begin()->s;
            a.erase({A[x], x});
            c.erase(c.begin());
            b.insert({B[x], x});
            d.insert({A[x] - B[x], x});
            a.insert({A[i], i});
            c.insert({B[i] - A[i], i});
            sum = val1;
            continue;
        }
        if(mx == val2){
            erase1();
            a.insert({A[i], i});
            a.insert({B[i] - A[i], i});
            sum = val2;
            continue;
        }
        if(mx == val3){
            erase1();
            int x = d.begin()->s;
            b.erase({B[x], x});
            d.erase(d.begin());
            a.insert({A[x], x});
            c.insert({B[x] - A[x], x});
            b.insert({B[i], i});
            d.insert({A[i] - B[i], i});
            sum = val3;
            continue;
        }
        if(mx == val4){
            erase2();
            b.insert({B[i], i});
            d.insert({A[i] - B[i], i});
            sum = val3;
            continue;
        }
    }
    cout << sum;
    return 0;
}

• Subtask 1: 20 / 100