Submission #81809

#	Time	Username	Problem	Language	Result	Execution time	Memory
81809		mra2322001	Schools (IZhO13_school)	C++14	95 / 100	173 ms	9668 KiB

school

#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const ll N = 300002;

int n, m, s, a[N], b[N], id[N];
ll ans1[N], ans2[N];

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> m >> s;
    f1(i, n){
        cin >> a[i] >> b[i];
        id[i] = i;
    }
    sort(id + 1, id + n + 1, [&](ll a1, ll a2){
         return a[a1] - b[a1] > a[a2] - b[a2];
    });
    priority_queue <int, vector <int>, greater <int> > q;
    f1(i, n){
        if(q.size() < m){
            ans1[i] = ans1[i - 1] + a[id[i]];
            q.push(a[id[i]]);
        }
        else{
            int x = q.top();
            q.pop();
            q.push(a[id[i]]);
            ans1[i] = ans1[i - 1] - x + a[id[i]];
        }
    }
    while(q.size()) q.pop();
    for(ll i = n; i >= 1; i--){
        if(q.size() < s){
            ans2[i] = ans2[i + 1] + b[id[i]];
            q.push(b[id[i]]);
        }
        else{
            int x = q.top();
            q.pop();
            q.push(b[id[i]]);
            ans2[i] = ans2[i + 1] - x + b[id[i]];
        }
    }
    f1(i, n) ans1[i] = max(ans1[i], ans1[i - 1]);
    for(ll i = n; i >= 1; i--) ans2[i] = max(ans2[i + 1], ans2[i]);
    ll res = LLONG_MIN;
    f1(i, n){
        if(i >= m && n - i >= s) res = max(res, ans1[i] + ans2[i +1]);
    }
    cout << res;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:25:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(q.size() < m){
            ~~~~~~~~~^~~
school.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(q.size() < s){
            ~~~~~~~~~^~~

• Subtask 1: 95 / 100