oj.uz

Submission #81806

# Submission time Handle Problem Language Result Execution time Memory
81806 2018-10-27T00:55:19 Z mra2322001 Schools (IZhO13_school) C++14
70 / 100
 169 ms 24852 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const int N = 300002;

int n, m, s, a[N], b[N], id[N], ans1[N], ans2[N];

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> m >> s;
    f1(i, n){
        cin >> a[i] >> b[i];
        id[i] = i;
    }
    sort(id + 1, id + n + 1, [&](int a1, int a2){
         return a[a1] - b[a1] > a[a2] - b[a2];
    });
    priority_queue <int, vector <int>, greater <int> > q;
    f1(i, n){
        if(q.size() < m){
            ans1[i] = ans1[i - 1] + a[id[i]];
            q.push(a[id[i]]);
        }
        else{
            int x = q.top();
            q.pop();
            q.push(a[id[i]]);
            ans1[i] = ans1[i - 1] - x + a[id[i]];
        }
    }
    while(q.size()) q.pop();
    for(int i = n; i >= 1; i--){
        if(q.size() < s){
            ans2[i] = ans2[i + 1] + b[id[i]];
            q.push(b[id[i]]);
        }
        else{
            int x = q.top();
            q.pop();
            q.push(b[id[i]]);
            ans2[i] = ans2[i + 1] - x + b[id[i]];
        }
    }
    f1(i, n) ans1[i] = max(ans1[i], ans1[i - 1]);
    for(int i = n; i >= 1; i--) ans2[i] = max(ans2[i + 1], ans2[i]);
    int res = INT_MIN;
    f1(i, n){
        if(i >= m && n - i >= s) res = max(res, ans1[i] + ans2[i +1]);
    }
    cout << res;
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:24:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(q.size() < m){
            ~~~~~~~~~^~~
school.cpp:37:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(q.size() < s){
            ~~~~~~~~~^~~

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 6 ms 820 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 2 ms 820 KB Output is correct
4 Correct 3 ms 820 KB Output is correct
5 Correct 2 ms 820 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 6 ms 992 KB Output is correct
8 Correct 5 ms 1176 KB Output is correct
9 Correct 4 ms 1240 KB Output is correct
10 Correct 4 ms 1240 KB Output is correct
11 Correct 4 ms 1264 KB Output is correct
12 Correct 4 ms 1340 KB Output is correct
13 Correct 32 ms 2548 KB Output is correct
14 Correct 41 ms 4228 KB Output is correct
15 Correct 80 ms 7464 KB Output is correct
16 Incorrect 95 ms 10700 KB Output isn't correct
17 Incorrect 128 ms 13704 KB Output isn't correct
18 Incorrect 155 ms 16848 KB Output isn't correct
19 Incorrect 154 ms 20260 KB Output isn't correct
20 Incorrect 169 ms 24852 KB Output isn't correct