제출 #167924

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167924		achibasadzishvili	학교 설립 (IZhO13_school)	C++14	15 / 100	172 ms	25016 KiB

school

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,m,s,prea[500005],preb[500005],ans,cur,fix[500005],raod,ind;
ll af[500005],bf[500005],pown = 1;
pair<ll,ll>t[5000005],a[400005],b[400005];
void upd(ll x){
    if(!x)return;
    t[x].f = t[2 * x].f + t[2 * x + 1].f;
    t[x].s = t[2 * x].s + t[2 * x + 1].s;
    upd(x / 2);
}
void ad(ll x){
    ll f = af[x] - bf[x] + 100005;
    t[pown + f - 1].f = 1;
    t[pown + f - 1].s = af[x] - bf[x];
    upd((pown + f - 1) / 2);
}
void rem(ll x){
    ll f = af[x] - bf[x] + 100005;
    t[pown + f - 1].f = 0;
    t[pown + f - 1].s = 0;
    upd((pown + f - 1) / 2);
}
void countt(ll x,ll L,ll R){
    if(t[x].f <= raod){
        raod -= t[x].f;
        cur += t[x].s;
        return;
    }
    if(L == R)return;
    
    if(t[2 * x].f >= raod)
        countt(2 * x , L , (L + R) / 2);
    else {
        cur += t[2 * x].s;
        countt(2 * x + 1 , (L + R) / 2 + 1 , R);
    }
    
}
int main(){
    
    ios::sync_with_stdio(false);
    cin >> n >> m >> s;
    
    while(pown <= 1000000)
        pown *= 2;
    
    for(int i=1; i<=n; i++){
        cin >> a[i].f >> b[i].f;
        af[i] = a[i].f;
        bf[i] = b[i].f;
        a[i].s = b[i].s = i;
    }
    
    sort(a + 1 , a + n + 1);
    reverse(a + 1 , a + n + 1);
    sort(b + 1 , b + n + 1);
    reverse(b + 1 , b + n + 1);
    for(int i=1; i<=n; i++)
        prea[i] = prea[i - 1] + a[i].f;
    for(int i=1; i<=n; i++)
        preb[i] = preb[i - 1] + b[i].f;
    
    for(int i=1; i<=m; i++)
        fix[a[i].s] = 1;
    ll saerto = 0 , sumb = 0;
    for(int i=1; i<=n; i++){
        fix[b[i].s]++;
        if(fix[b[i].s] == 2){
            saerto++;
            if(m + i - saerto > s + m){
                saerto--;
                fix[b[i].s]--;
                break;
            }
            ad(b[i].s);
        }
        if(m + i - saerto > s + m){fix[b[i].s]--;break;}
        if(m + i - saerto <= s + m)ind = i;
    }
    for(int i=1; i<=ind; i++)
        if(fix[b[i].s] == 1)
            sumb += b[i].f;
    for(int i=m; i<=n; i++){
        if(i > m){
            fix[a[i].s]++;
            if(fix[a[i].s] == 2){
                saerto++;
                sumb -= bf[a[i].s];
                ad(a[i].s);
            }
        }
        while(i + ind - saerto > s + m){
            fix[b[ind].s]--;
            if(fix[b[ind].s] == 1){
                rem(b[ind].s);
                saerto--;
            }
            else {
                sumb -= b[ind].f;
            }
            ind--;
            if(ind < s)break;
        }
        if(ind < s)break;
        raod = i - m;
        cur = 0;
        countt(1 , 1 , pown);
        ans = max(ans , prea[i] + sumb - cur);
    }
    
    
    cout << ans << endl;
    
    
    return 0;
}

• Subtask 1: 15 / 100