Submission #672986

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

school

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef string str;

#define int long long
#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	2084 ms	212 KB	Time limit exceeded
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	596 KB	Output is correct
8	Correct	2 ms	724 KB	Output is correct
9	Correct	2 ms	596 KB	Output is correct
10	Correct	2 ms	724 KB	Output is correct
11	Correct	2 ms	596 KB	Output is correct
12	Correct	2 ms	724 KB	Output is correct
13	Correct	17 ms	3384 KB	Output is correct
14	Correct	30 ms	4944 KB	Output is correct
15	Correct	46 ms	8032 KB	Output is correct
16	Correct	124 ms	16168 KB	Output is correct
17	Correct	152 ms	15480 KB	Output is correct
18	Correct	146 ms	15908 KB	Output is correct
19	Correct	165 ms	17204 KB	Output is correct
20	Correct	206 ms	19872 KB	Output is correct