oj.uz

Submission #47574

# Submission time Handle Problem Language Result Execution time Memory
47574 2018-05-05T04:44:34 Z JohnTitor Schools (IZhO13_school) C++11
100 / 100
 229 ms 13612 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
typedef long long ll;
typedef long double ld;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "C"
int n, m, s;
class city{
public:
    ll a, b;
} c[300001];
ll f[300001];
ll g[300001];
multiset <ll> se;
ll sum;
int main(){
    #ifdef Kanikou
        if(fopen(taskname".inp", "r"))
            freopen(taskname".inp", "r", stdin);
    #endif // Kanikou
    read(n);
    read(m);
    read(s);
    FOR(i, 1, n){
        read(c[i].a);
        read(c[i].b);
    }
    sort(c+1, c+n+1, [](city A, city B){
        return A.a-A.b>B.a-B.b;
    });
    FOR(i, 1, m){
        se.insert(c[i].a);
        sum+=c[i].a;
    }
    f[m]=sum;
    FOR(i, m+1, n){
        se.insert(c[i].a);
        sum+=c[i].a;
        sum-=*se.begin();
        se.erase(se.begin());
        f[i]=sum;
    }
    se.clear();
    sum=0;
    FOR(i, 1, s){
        se.insert(c[n-i+1].b);
        sum+=c[n-i+1].b;
    }
    g[n-s+1]=sum;
    DFOR(i, n-s, 1){
        se.insert(c[i].b);
        sum+=c[i].b;
        sum-=*se.begin();
        se.erase(se.begin());
        g[i]=sum;
    }
    ll ans=0;
    FOR(i, m, n-s) ans=max(ans, f[i]+g[i+1]);
    writeln(ans);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 2 ms 488 KB Output is correct
7 Correct 3 ms 552 KB Output is correct
8 Correct 4 ms 744 KB Output is correct
9 Correct 4 ms 812 KB Output is correct
10 Correct 4 ms 848 KB Output is correct
11 Correct 4 ms 848 KB Output is correct
12 Correct 4 ms 888 KB Output is correct
13 Correct 24 ms 2864 KB Output is correct
14 Correct 40 ms 3760 KB Output is correct
15 Correct 57 ms 5776 KB Output is correct
16 Correct 150 ms 12184 KB Output is correct
17 Correct 184 ms 12184 KB Output is correct
18 Correct 191 ms 12184 KB Output is correct
19 Correct 202 ms 12184 KB Output is correct
20 Correct 229 ms 13612 KB Output is correct