제출 #343119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
343119		Gurban	학교 설립 (IZhO13_school)	C++17	100 / 100	289 ms	19652 KiB

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 / 100