Submission #47562

#	Time	Username	Problem	Language	Result	Execution time	Memory
47562		fallingstar	Schools (IZhO13_school)	C++17	100 / 100	459 ms	13164 KiB

school

/**
    Problem: Schools
    Source: IX Zhautykov Olympiad on Mathematics, Physics and Informatics (IZhO) 2013, day 1, problem C
*/

#include <iostream>
#include <algorithm>
#include <set>

#define long long long

using namespace std;

const int N = 3e5 + 2;

int n, m1, m2;
pair<int, int> a[N];
long fa[N], fb[N];

int main()
{
    cin >> n >> m1 >> m2;
    for (int i = 1; i <= n; ++i)
        cin >> a[i].first >> a[i].second;

    sort(a + 1, a + 1 + n, [](pair<int, int> a, pair<int, int> b) {
        return a.first - a.second > b.first - b.second;
    });

    set<pair<int, int> > s;
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = fa[i - 1] + a[i].first;
        s.insert({a[i].first, i});
        if (s.size() > m1)
        {
            fa[i] -= s.begin()->first;
            s.erase(s.begin());
        }
    }
    s.clear();
    for (int i = n; i >= 1; --i)
    {
        fb[i] = fb[i + 1] + a[i].second;
        s.insert({a[i].second, i});
        if (s.size() > m2)
        {
            fb[i] -= s.begin()->first;
            s.erase(s.begin());
        }
    }

    long res = 0;
    for (int i = m1; i + m2 <= n; ++i)
        res = max(res, fa[i] + fb[i + 1]);
    cout << res;
    return 0;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:35:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (s.size() > m1)
             ~~~~~~~~~^~~~
school.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (s.size() > m2)
             ~~~~~~~~~^~~~

• Subtask 1: 100 / 100