oj.uz

답안 #343119

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
343119 2021-01-03T12:28:00 Z Gurban 학교 설립 (IZhO13_school) C++17
100 / 100
 289 ms 19652 KB 
#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

# 결과 실행 시간 메모리 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