oj.uz

Submission #4801

# Submission time Handle Problem Language Result Execution time Memory
4801 2014-01-04T07:21:55 Z cki86201 Schools (IZhO13_school) C++
100 / 100
 236 ms 11512 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5936 KB Output is correct
2 Correct 0 ms 5936 KB Output is correct
3 Correct 0 ms 5936 KB Output is correct
4 Correct 0 ms 5936 KB Output is correct
5 Correct 0 ms 5936 KB Output is correct
6 Correct 0 ms 5936 KB Output is correct
7 Correct 0 ms 5936 KB Output is correct
8 Correct 0 ms 6084 KB Output is correct
9 Correct 0 ms 6084 KB Output is correct
10 Correct 0 ms 5936 KB Output is correct
11 Correct 4 ms 5936 KB Output is correct
12 Correct 4 ms 5936 KB Output is correct
13 Correct 24 ms 7100 KB Output is correct
14 Correct 56 ms 6580 KB Output is correct
15 Correct 100 ms 6068 KB Output is correct
16 Correct 172 ms 11192 KB Output is correct
17 Correct 172 ms 11200 KB Output is correct
18 Correct 184 ms 10488 KB Output is correct
19 Correct 216 ms 11512 KB Output is correct
20 Correct 236 ms 11512 KB Output is correct