oj.uz

Submission #672993

# Submission time Handle Problem Language Result Execution time Memory
672993 2022-12-19T10:31:28 Z viwlesxq Schools (IZhO13_school) C++17
100 / 100
 177 ms 15060 KB 
#include "bits/stdc++.h"
using namespace std;
 
typedef long long ll;
typedef string str;
 
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, s;
	cin >> n >> m >> s;
	int a[n], b[n];
	vector <pair <int, int>> v;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		v.pb({a[i] - b[i], i});
	}
	if (!m && !s) {
		cout << 0;
		return 0;
	}
	if (!s) {
		sort(a, a + n);
		reverse(a, a + n);
		ll ans = 0;
		for (int i = 0; i < m; i++) ans += a[i];
		cout << ans;
		return 0;
	}
	if (!m) {
		sort(b, b + n);
		reverse(b, b + n);
		ll ans = 0;
		for (int i = 0; i < s; i++) ans += b[i];
		cout << ans;
		return 0;
	}
	sort(rall(v));
	multiset <int> cur;
	ll sum = 0;
	for (int i = 0; i < m; i++) {
		cur.insert(a[v[i].S]);
		sum += a[v[i].S];
	}
	ll pref[n], suff[n];
	pref[m-1] = sum;
	for (int i = m; i < n; i++) {
		int can = a[v[i].S];
		if (*cur.begin() < can) {
			sum -= *cur.begin();
			cur.erase(cur.begin());
			cur.insert(can);
			sum += can;
		}
		pref[i] = sum;
	}
	sum = 0;
	cur.clear();
	for (int i = n - 1; i >= n - s; i--) {
		cur.insert(b[v[i].S]);
		sum += b[v[i].S];
	}
	suff[n-s] = sum;
	for (int i = n - s - 1; i >= 0; i--) {
		int can = b[v[i].S];
		if (*cur.begin() < can) {
			sum -= *cur.begin();
			cur.erase(cur.begin());
			cur.insert(can);
			sum += can;
		}
		suff[i] = sum;
	}
	ll ans = 0;
	for (int i = m - 1; i < n - s; i++) {
		ans = max(ans, pref[i] + suff[i+1]);
	}
	cout << ans;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 624 KB Output is correct
9 Correct 3 ms 580 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 16 ms 2900 KB Output is correct
14 Correct 31 ms 3788 KB Output is correct
15 Correct 42 ms 5532 KB Output is correct
16 Correct 116 ms 13280 KB Output is correct
17 Correct 135 ms 12124 KB Output is correct
18 Correct 177 ms 12072 KB Output is correct
19 Correct 158 ms 13176 KB Output is correct
20 Correct 176 ms 15060 KB Output is correct