oj.uz

답안 #167926

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167926 2019-12-10T20:11:13 Z achibasadzishvili 학교 설립 (IZhO13_school) C++14
35 / 100
 171 ms 23792 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 = 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){
        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
35.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 Incorrect 2 ms 504 KB Output isn't correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 1528 KB Output is correct
7 Incorrect 4 ms 1144 KB Output isn't correct
8 Incorrect 6 ms 2936 KB Output isn't correct
9 Incorrect 6 ms 2424 KB Output isn't correct
10 Correct 5 ms 1912 KB Output is correct
11 Incorrect 5 ms 2040 KB Output isn't correct
12 Incorrect 5 ms 1656 KB Output isn't correct
13 Incorrect 22 ms 4732 KB Output isn't correct
14 Incorrect 41 ms 7276 KB Output isn't correct
15 Correct 81 ms 12920 KB Output is correct
16 Incorrect 119 ms 16504 KB Output isn't correct
17 Incorrect 136 ms 18556 KB Output isn't correct
18 Incorrect 139 ms 19576 KB Output isn't correct
19 Incorrect 151 ms 21752 KB Output isn't correct
20 Incorrect 171 ms 23792 KB Output isn't correct