Submission #641604

#	Time	Username	Problem	Language	Result	Execution time	Memory
641604		andreast12	Schools (IZhO13_school)	C++17	100 / 100	85 ms	6232 KiB

school

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
const int mod=998244353, maxn=3e5+5;
int n, m, s;
pair<int, int> a[maxn];
priority_queue<int, vector<int>, greater<int>> pq;
ll val, pf[maxn], sf[maxn], ans;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m >> s;
	for(int i=1; i<=n; i++) cin >> a[i].fi >> a[i].se;
	sort(a+1, a+n+1, [](auto ki, auto ka) {
		return ki.fi-ki.se>ka.fi-ka.se;
	});
	for(int i=1; i<=m; i++) {
		pq.push(a[i].fi);
		val+=a[i].fi;
		if(i==m) pf[i]=val;
	}
	for(int i=m+1; i<=n; i++) {
		if(!pq.empty()&&a[i].fi>pq.top()) {
			val+=a[i].fi-pq.top();
			pq.pop();
			pq.push(a[i].fi);
		}
		pf[i]=val;
	}
	val=0;
	while(!pq.empty()) pq.pop();
	for(int i=n; i>=n-s+1; i--) {
		pq.push(a[i].se);
		val+=a[i].se;
		if(i==n-s+1) sf[i]=val;
	}
	for(int i=n-s; i>0; i--) {
		if(!pq.empty()&&a[i].se>pq.top()) {
			val+=a[i].se-pq.top();
			pq.pop();
			pq.push(a[i].se);
		}
		sf[i]=val;
	}
	for(int i=m; i<=n-s; i++) ans=max(ans, pf[i]+sf[i+1]);
	cout << ans << '\n';
}

• Subtask 1: 100 / 100