oj.uz

Submission #848617

# Submission time Handle Problem Language Result Execution time Memory
848617 2023-09-13T04:55:39 Z wakandaaa Schools (IZhO13_school) C++17
100 / 100
 86 ms 12496 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n, m, s;
pair<int, int> a[N];
int f[N], g[N];

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

    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);

    cin >> n >> m >> s;
    for (int i = 1; i <= n; ++i) 
    	cin >> a[i].fi >> a[i].se;

    sort(a + 1, a + n + 1, [&] (pair<int, int> x, pair<int, int> y) {
    	return x.fi - x.se > y.fi - y.se;
    });

    priority_queue<int, vector<int>, greater<int> > q;

    for (int i = 1; i <= n; ++i) {
    	f[i] = f[i - 1] + a[i].fi;
    	q.push(a[i].fi);
    	if ((int) q.size() > m) {
    		f[i] -= q.top();
    		q.pop();
    	}
    }

    while (q.size()) q.pop();

    for (int i = n; i >= 1; --i) {
    	g[i] = g[i + 1] + a[i].se;
    	q.push(a[i].se);
    	if ((int) q.size() > s) {
    		g[i] -= q.top();
    		q.pop();
    	}
    }

    int res = 0;
    for (int i = m; i <= n - s; ++i) res = max(res, f[i] + g[i + 1]);

    cout << res;

    return 0;
}

/*

*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 2 ms 2648 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 2 ms 2648 KB Output is correct
13 Correct 11 ms 3296 KB Output is correct
14 Correct 21 ms 7896 KB Output is correct
15 Correct 37 ms 8528 KB Output is correct
16 Correct 49 ms 10192 KB Output is correct
17 Correct 65 ms 11724 KB Output is correct
18 Correct 72 ms 11724 KB Output is correct
19 Correct 77 ms 11984 KB Output is correct
20 Correct 86 ms 12496 KB Output is correct