Submission #4798

#	Time	Username	Problem	Language	Result	Execution time	Memory
4798		cki86201	Schools (IZhO13_school)	C++98	25 / 100	204 ms	7780 KiB

school

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

typedef long long ll;
int N,M,S;
bool chk[300030][2];
ll ans;

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

priority_queue <int,vector<int>,greater<int> >pq1;
priority_queue <int> pq2,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])pq3.push(inp[i].y-inp[i].x);
		else if(chk[i][0])pq1.push(inp[i].x);
		else if(chk[i][1])pq2.push(inp[i].y);
	}
	pq2.push(-1e9),pq3.push(-1e9),pq1.push(1e9);
	for(i=0;i<S;i++){
		int a = pq3.top();
		int b = pq2.top() - pq1.top();
		if(a>b)pq3.pop(), ans += a;
		else pq2.pop(), pq1.pop(), ans += b;
	}
	printf("%lld",ans);
	return 0;
}

• Subtask 1: 25 / 100