Submission #343119

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
343119	2021-01-03T12:28:00 Z	Gurban	Schools (IZhO13_school)	C++17	100 / 100	289 ms	19652 KB

school

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

using ll = long long;

const int maxn=3e5+5;
int n,s[2],a[maxn],b[maxn];
ll cep[maxn],sag[maxn],nw;
vector<pair<int,int>>v;
vector<int>a_s,b_s;
multiset<int>m;
ll ans;

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

	cin >> n >> s[0] >> s[1];
	for(int i = 1;i <= n;i++){
		cin >> a[i] >> b[i];
		a_s.push_back(-a[i]);
		b_s.push_back(-b[i]);
		v.push_back({a[i]-b[i],i});
	}
	sort(a_s.begin(),a_s.end());
	sort(b_s.begin(),b_s.end());
	if(s[0] == 0){
		for(int i = 0;i < s[1];i++) ans -= b_s[i];
		return cout<<ans,0; 
	}
	if(s[1]==0){
		for(int i = 0;i < s[0];i++) ans -= a_s[i];
		return cout<<ans,0;
	}
	sort(v.begin(),v.end());
	reverse(v.begin(),v.end());
	for(int i = 0;i < s[0];i++) m.insert(a[v[i].second]),nw += a[v[i].second],cep[i]=-1e9;
	cep[s[0]-1] = nw;
	for(int i = s[0];i < (int)v.size();i++){
		if(!m.empty() and *m.begin() < a[v[i].second]){
			nw -= *m.begin();
			nw += a[v[i].second];
			m.erase(m.begin());
			m.insert(a[v[i].second]);
		}
		cep[i] = nw;
	}

	m.clear(); nw = 0;
	for(int i = (int)v.size()-1;i >= (int)v.size()-s[1];i--) m.insert(b[v[i].second]),nw += b[v[i].second],sag[i]=-1e9;
	sag[(int)v.size() - s[1]] = nw;
	
	for(int i = (int)v.size()-s[1]-1;i >= 0;i--){
		if(!m.empty() and *m.begin() < b[v[i].second]){
			nw -= *m.begin();
			nw += b[v[i].second];
			m.erase(m.begin());
			m.insert(b[v[i].second]);
		}
		sag[i] = nw;
	}
	for(int i = 0;i < (int)v.size() - 1;i++) ans = max(ans,cep[i]+sag[i+1]);
	cout<<ans;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	3 ms	620 KB	Output is correct
8	Correct	3 ms	876 KB	Output is correct
9	Correct	4 ms	748 KB	Output is correct
10	Correct	3 ms	748 KB	Output is correct
11	Correct	4 ms	748 KB	Output is correct
12	Correct	4 ms	876 KB	Output is correct
13	Correct	28 ms	3736 KB	Output is correct
14	Correct	51 ms	4828 KB	Output is correct
15	Correct	85 ms	8672 KB	Output is correct
16	Correct	188 ms	16848 KB	Output is correct
17	Correct	209 ms	15952 KB	Output is correct
18	Correct	224 ms	15824 KB	Output is correct
19	Correct	244 ms	17488 KB	Output is correct
20	Correct	289 ms	19652 KB	Output is correct