oj.uz

답안 #167927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167927 2019-12-10T20:11:52 Z achibasadzishvili 학교 설립 (IZhO13_school) C++14
35 / 100
 170 ms 23928 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){
        if(raod)while(true);
        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 1400 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 23 ms 4728 KB Output isn't correct
14 Incorrect 42 ms 7288 KB Output isn't correct
15 Correct 82 ms 12916 KB Output is correct
16 Incorrect 119 ms 16504 KB Output isn't correct
17 Incorrect 134 ms 17784 KB Output isn't correct
18 Incorrect 138 ms 19256 KB Output isn't correct
19 Incorrect 150 ms 20600 KB Output isn't correct
20 Incorrect 170 ms 23928 KB Output isn't correct