Submission #11213171

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;

struct node{
	LL id,lr,val;
	bool operator <(const node &nd)const{
		return nd.val > val;
	}
};
priority_queue <node> q;

node make_node(LL id,LL lr,LL val){
	node ret; ret.id = id; ret.lr = lr; ret.val = val; return ret;
}

LL n,l[500005],r[500005],sl = 0,sr = 0;
LL in[500005][2] = {0};
LL h[500005],hd[500005],sum = 0,ans = INF;

int main(){
	cin >> n;
	for(LL i = 1;i <= n;i ++){
		cin >> l[i] >> r[i]; sl += l[i]; sr += r[i];
		in[i][0] = 1; in[i][1] = 1;
		q.push(make_node(i,0,l[i]));
		if(q.size() > n){ in[q.top().id][q.top().lr] = 0; q.pop(); }
		q.push(make_node(i,1,r[i]));
		if(q.size() > n){ in[q.top().id][q.top().lr] = 0; q.pop(); }
	}
	for(LL i = 1;i <= n;i ++){
		h[i] = q.top().val; sum += h[i]; hd[i] = q.top().id;
		q.pop();
	}
	for(LL i = 1;i <= n;i ++){
		LL tmp = sum,tt = 0;
		if(!in[i][0] && !in[i][1]){
			tmp += l[i]; tmp += r[i];
			tmp -= h[1]; tmp -= h[2];
		}
		if(!in[i][0] && in[i][1]){
			tmp += l[i];
			tmp -= (hd[1] == i ? h[2] : h[1]);
		}
		if(!in[i][1] && in[i][0]){
			tmp += r[i];
			tmp -= (hd[1] == i ? h[2] : h[1]);
		}
//		cout << i << ' ' << tmp << ' ' << sum << endl;
		ans = min(ans,tmp);
	}
	ans = min(ans,min(sl,sr));
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result