oj.uz

Submission #897089

# Submission time Handle Problem Language Result Execution time Memory
897089 2024-01-02T14:22:22 Z borisAngelov Schools (IZhO13_school) C++17
100 / 100
 270 ms 31368 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 300005;

int n, music, sport;

pair<int, int> a[maxn];

multiset<pair<int, pair<int, int>>, greater<pair<int, pair<int, int>>>> currentMusic;
multiset<pair<int, int>, greater<pair<int, int>>> otherByMusic;
multiset<pair<int, int>, greater<pair<int, int>>> otherBySport;

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> music >> sport;

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

    sort(a + 1, a + n + 1, greater<pair<int, int>>());

    long long ans = 0;

    for (int i = 1; i <= music; ++i)
    {
        ans += a[i].first;
        currentMusic.insert({a[i].second - a[i].first, {a[i].first, a[i].second}});
    }

    for (int i = music + 1; i <= n; ++i)
    {
        otherByMusic.insert({a[i].first, a[i].second});
        otherBySport.insert({a[i].second, a[i].first});
    }

    for (int steps = 1; steps <= sport; ++steps)
    {
        long long case1 = 0, case2 = 0;

        //long long case1 = (*otherBySport.begin());
        //long long case2 = (*currentMusic.begin()) + (*otherByMusic.begin());

        pair<int, int> currSport = (*otherBySport.begin());
        case1 = currSport.first;

        pair<int, pair<int, int>> currMus = (*currentMusic.begin());
        pair<int, int> otherMus = (*otherByMusic.begin());
        case2 = currMus.first + otherMus.first;

        if (case1 >= case2)
        {
            ans += case1;

            auto it = otherBySport.begin();

            int x = it -> first;
            int y = it -> second;

            otherBySport.erase(otherBySport.find({x, y}));
            otherByMusic.erase(otherByMusic.find({y, x}));
        }
        else
        {
            ans += case2;

            auto it = currentMusic.begin();
            pair<int, pair<int, int>> curr = *it;

            currentMusic.erase(currentMusic.find(curr));

            pair<int, int> currMusic = (*otherByMusic.begin());
            otherByMusic.erase(otherByMusic.find(currMusic));
            otherBySport.erase(otherBySport.find({currMusic.second, currMusic.first}));

            currentMusic.insert({currMusic.second - currMusic.first, currMusic});
        }
    }

    cout << ans << endl;

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 4 ms 860 KB Output is correct
13 Correct 20 ms 5468 KB Output is correct
14 Correct 53 ms 10580 KB Output is correct
15 Correct 149 ms 19092 KB Output is correct
16 Correct 238 ms 21044 KB Output is correct
17 Correct 187 ms 23120 KB Output is correct
18 Correct 198 ms 24928 KB Output is correct
19 Correct 230 ms 27084 KB Output is correct
20 Correct 270 ms 31368 KB Output is correct