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

school

#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)
             ~~~~~~~~~~~^~~~

Subtask #1

100.0 / 100.0

#	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