oj.uz

Submission #83708

# Submission time Handle Problem Language Result Execution time Memory
83708 2018-11-10T03:35:00 Z mra2322001 Schools (IZhO13_school) C++14
100 / 100
 129 ms 8308 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;
ll ans1[N], ans2[N];
pair <int, int> a[N];

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

    cin >> n >> m >> s;
    f1(i, n) cin >> a[i].first >> a[i].second;

    sort(a + 1, a + n + 1, [&](pair <int, int> a1, pair <int, int> a2){
         return a1.first - a1.second > a2.first - a2.second;
    });

    priority_queue <int, vector <int>, greater <int> > q;
    if(m > 0){
        f1(i, n){
            if(i <= m){
                ans1[i] = ans1[i - 1] + a[i].first;
                q.push(a[i].first);
            }
            else{
                ans1[i] = max(ans1[i - 1] - q.top() + a[i].first, ans1[i - 1]);
                if(q.top() <= a[i].first){
                    q.pop();
                    q.push(a[i].first);
                }
            }
        }
    }
    while(q.size()) q.pop();
    if(s > 0){
        for(int i = n; i >= 1; i--){
            if(n - i + 1 <= s){
                ans2[i] = ans2[i + 1] +a[i].second;
                q.push(a[i].second);
            }
            else{
                ans2[i] = max(ans2[i + 1], ans2[i + 1] - q.top() + a[i].second);
                if(ans2[i] != ans2[i + 1]){
                    q.pop();
                    q.push(a[i].second);
                }
            }
        }
    }
    ll ans = 0;
    f0(i, n + 1){
        if(i >= m && n - i >= s) ans = max(ans, ans1[i] + ans2[i + 1]);
    }
    cout << ans;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 424 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 4 ms 748 KB Output is correct
8 Correct 4 ms 752 KB Output is correct
9 Correct 4 ms 796 KB Output is correct
10 Correct 4 ms 796 KB Output is correct
11 Correct 4 ms 924 KB Output is correct
12 Correct 4 ms 924 KB Output is correct
13 Correct 20 ms 1784 KB Output is correct
14 Correct 32 ms 2808 KB Output is correct
15 Correct 57 ms 4544 KB Output is correct
16 Correct 77 ms 5748 KB Output is correct
17 Correct 92 ms 6388 KB Output is correct
18 Correct 129 ms 7020 KB Output is correct
19 Correct 107 ms 7408 KB Output is correct
20 Correct 123 ms 8308 KB Output is correct