Submission #672985

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
672985	2022-12-19T10:03:14 Z	viwlesxq	Schools (IZhO13_school)	C++17	95 / 100	2000 ms	15040 KB

school

#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});
	}
	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

95.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Execution timed out	2074 ms	212 KB	Time limit exceeded
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 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	596 KB	Output is correct
9	Correct	2 ms	596 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	17 ms	2912 KB	Output is correct
14	Correct	30 ms	3664 KB	Output is correct
15	Correct	42 ms	5528 KB	Output is correct
16	Correct	111 ms	13280 KB	Output is correct
17	Correct	151 ms	12156 KB	Output is correct
18	Correct	160 ms	12084 KB	Output is correct
19	Correct	154 ms	13160 KB	Output is correct
20	Correct	181 ms	15040 KB	Output is correct