oj.uz

Submission #47562

# Submission time Handle Problem Language Result Execution time Memory
47562 2018-05-05T03:49:00 Z fallingstar Schools (IZhO13_school) C++17
100 / 100
 459 ms 13164 KB 
/**
    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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 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 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 6 ms 684 KB Output is correct
8 Correct 7 ms 816 KB Output is correct
9 Correct 7 ms 816 KB Output is correct
10 Correct 7 ms 816 KB Output is correct
11 Correct 7 ms 816 KB Output is correct
12 Correct 7 ms 900 KB Output is correct
13 Correct 44 ms 2908 KB Output is correct
14 Correct 82 ms 3404 KB Output is correct
15 Correct 156 ms 4692 KB Output is correct
16 Correct 240 ms 12220 KB Output is correct
17 Correct 312 ms 12220 KB Output is correct
18 Correct 341 ms 12220 KB Output is correct
19 Correct 355 ms 12220 KB Output is correct
20 Correct 459 ms 13164 KB Output is correct