Submission #90535

#	Time	Username	Problem	Language	Result	Execution time	Memory
90535		popovicirobert	Schools (IZhO13_school)	C++14	95 / 100	2048 ms	12972 KiB

school

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 3e5;

pair <int, int> arr[MAXN + 1];

bool cmp(pair <int, int> a, pair <int, int> b) {
    /*if(a.first - a.second == b.first - b.second) {
        return a.second < b.second;
    }*/
    return a.first - a.second > b.first - b.second;
}

ll pref[MAXN + 1], suff[MAXN + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m, s;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> s;
    for(i = 1; i <= n; i++) {
        cin >> arr[i].first >> arr[i].second;
    }
    sort(arr + 1, arr + n + 1, cmp);
    multiset <int> mst;
    ll cur = 0;
    for(i = 1; i <= n; i++) {
        if(mst.size() < m) {
            mst.insert(arr[i].first);
            cur += arr[i].first;
        }
        else if(*mst.begin() < arr[i].first) {
            cur -= *mst.begin();
            mst.erase(mst.begin());
            mst.insert(arr[i].first);
            cur += arr[i].first;
        }
        pref[i] = cur;
    }
    mst.clear();
    cur = 0;
    for(i = n; i >= 1; i--) {
        if(mst.size() < s) {
            mst.insert(arr[i].second);
            cur += arr[i].second;
        }
        else if(*mst.begin() < arr[i].second) {
            cur -= *mst.begin();
            mst.erase(mst.begin());
            mst.insert(arr[i].second);
            cur += arr[i].second;
        }
        suff[i] = cur;
    }
    ll ans = 0;
    for(i = m; i <= n - s; i++) {
        ans = max(ans, pref[i] + suff[i + 1]);
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 95 / 100