Submission #4801

#	Time	Username	Problem	Language	Result	Execution time	Memory
4801		cki86201	Schools (IZhO13_school)	C++98	100 / 100	236 ms	11512 KiB

school

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<functional>
using namespace std;

#define X first
#define Y second
typedef long long ll;
typedef pair<int,int> Pi;
int N,M,S;
bool chk[300030][2];
bool chk1[300030],chk2[300030];
ll ans;

struct data{
	int x,y,c;
	bool operator<(const data &l)const{
		return c<l.c;
	}
}inp[300030];

priority_queue <Pi, vector<Pi>, greater<Pi> >pq1;
priority_queue <Pi> pq2;
priority_queue <int> pq3;

bool compx(const data &a,const data &b){return a.x<b.x;}
bool compy(const data &a,const data &b){return a.y<b.y;}

int main(){
	scanf("%d%d%d",&N,&M,&S);
	int i;
	for(i=0;i<N;i++){
		scanf("%d%d",&inp[i].x,&inp[i].y);
		inp[i].c=i;
	}
	sort(inp,inp+N,compx);
	for(i=N-M-S;i<N;i++)ans += inp[i].x, chk[inp[i].c][0] = 1;
	sort(inp,inp+N,compy);
	for(i=N-M-S;i<N;i++)chk[inp[i].c][1] = 1;
	sort(inp,inp+N);
	for(i=0;i<N;i++){
		if(chk[i][0]&&chk[i][1]){
			pq2.push(Pi(inp[i].y-inp[i].x,i));
			pq1.push(Pi(inp[i].x,i));
		}
		else if(chk[i][0])pq1.push(Pi(inp[i].x,i));
		else if(chk[i][1])pq3.push(inp[i].y);
	}
	pq1.push(Pi(1e9,1)), pq2.push(Pi(-1e9,1)), pq3.push(-1e9);
	for(i=0;i<S;i++){
		Pi a = pq1.top(), b = pq2.top();
		while(chk1[a.Y])pq1.pop(), a = pq1.top();
		while(chk2[b.Y])pq2.pop(), b = pq2.top();
		int c = pq3.top();
		if(b.X >= c - a.X)ans += b.X, pq2.pop(), chk1[b.Y] = 1;
		else{
			ans += c - a.X;
			pq3.pop(),pq1.pop();
			if(chk[a.Y][1])chk2[a.Y] = 1, pq3.push(inp[a.Y].y);
		}
	}
	printf("%lld",ans);
	return 0;
}

• Subtask 1: 100 / 100