Submission #242611

# Submission time Handle Problem Language Result Execution time Memory
242611 2020-06-28T10:34:10 Z apostoldaniel854 Schools (IZhO13_school) C++14
100 / 100
168 ms 9200 KB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << "\n"

/**
-   we want to find to disjoint subsets of indices X (|X| = M) and Y (|Y| = S) so that sum{a[i]|i belongs to X} + sum{b[i]|i belongs to Y}
-   it's easy to prove that if we sort the indices by b[i] - a[i] we will not use a a[i] and b[j] with i > j
-   now we can see the best solution for a on prefix and the best solution for b on suffix and combine them
**/

const int N = 3e5;

int a[1 + N], b[1 + N];
int order[1 + N];

bool cmp (int x, int y) {
    return b[x] - a[x] < b[y] - a[y];
}

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

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int n, M, S;
    cin >> n >> M >> S;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        order[i] = i;
    }
    sort (order + 1, order + n + 1, cmp);

    /// make pref
    ll sum = 0;
    priority_queue <int> pq;
    if (M == 0)
        pref[0] = 0;
    else
        pref[0] = -1;
    for (int i = 1; i <= n; i++) {
        int index = order[i];
        pq.push (-a[index]);
        sum += a[index];
        if (pq.size () > M) {
            sum += pq.top ();
            pq.pop ();
        }
        if (pq.size () == M)
            pref[i] = sum;
        else
            pref[i] = -1;
    }
    /// make suff
    while (pq.size ()) pq.pop ();
    sum = 0;
    if (S == 0)
        suff[n + 1] = 0;
    else
        suff[n + 1] = -1;
    for (int i = n; i > 0; i--) {
        int index = order[i];
        pq.push (-b[index]);
        sum += b[index];
        if (pq.size () > S) {
            sum += pq.top ();
            pq.pop ();
        }
        if (pq.size () == S)
            suff[i] = sum;
        else
            suff[i] = -1;
    }
    ll ans = 0;
    for (int i = 0; i <= n; i++)
        if (pref[i] != -1 && suff[i + 1] != -1)
            ans = max (ans, pref[i] + suff[i + 1]);
    cout << ans << "\n";
    return 0;
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:49:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pq.size () > M) {
             ~~~~~~~~~~~^~~
school.cpp:53:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pq.size () == M)
             ~~~~~~~~~~~^~~~
school.cpp:69:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pq.size () > S) {
             ~~~~~~~~~~~^~~
school.cpp:73:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pq.size () == S)
             ~~~~~~~~~~~^~~~
# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 6 ms 512 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 23 ms 1536 KB Output is correct
14 Correct 41 ms 2680 KB Output is correct
15 Correct 74 ms 4728 KB Output is correct
16 Correct 90 ms 6004 KB Output is correct
17 Correct 123 ms 6904 KB Output is correct
18 Correct 132 ms 7412 KB Output is correct
19 Correct 152 ms 7920 KB Output is correct
20 Correct 168 ms 9200 KB Output is correct