oj.uz

답안 #167930

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167930 2019-12-10T20:17:29 Z achibasadzishvili 학교 설립 (IZhO13_school) C++14
100 / 100
 176 ms 24312 KB 
#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++;
    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--;
    t[pown + f - 1].s -= af[x] - bf[x];
    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){
        cur += raod * (t[x].s / t[x].f);
        return;
    }
    
    if(t[2 * x].f >= raod)
        countt(2 * x , L , (L + R) / 2);
    else {
        cur += t[2 * x].s;
        raod -= t[2 * x].f;
        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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 3 ms 1400 KB Output is correct
7 Correct 4 ms 1144 KB Output is correct
8 Correct 6 ms 2936 KB Output is correct
9 Correct 6 ms 2424 KB Output is correct
10 Correct 5 ms 1912 KB Output is correct
11 Correct 5 ms 2040 KB Output is correct
12 Correct 5 ms 1656 KB Output is correct
13 Correct 22 ms 4728 KB Output is correct
14 Correct 41 ms 7416 KB Output is correct
15 Correct 82 ms 12972 KB Output is correct
16 Correct 128 ms 16496 KB Output is correct
17 Correct 139 ms 18128 KB Output is correct
18 Correct 141 ms 19576 KB Output is correct
19 Correct 156 ms 22008 KB Output is correct
20 Correct 176 ms 24312 KB Output is correct