Cod sursa(job #194151)

Utilizator swift90Ionut Bogdanescu swift90 Data 8 iunie 2008 16:34:19
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int,int> nr[50100];
int vx[50100],vy[50100];
int main(){
	freopen("tribute.in","r",stdin);
	freopen("tribute.out","w",stdout);
	int n,dx,dy,i;
	int ss,sd,minim,maxim=0,maxi=0,suma;
	scanf("%d",&n);
	scanf("%d%d",&dx,&dy);
	for(i=0;i<n;++i){
		scanf("%d%d",&nr[i].first,&nr[i].second);
		++vx[nr[i].first];
		++vy[nr[i].second];
		if(nr[i].first>maxim)
			maxim=nr[i].first;
		if(nr[i].second>maxi)
			maxi=nr[i].second;
	}
	ss=sd=0;
	for(i=1;i<=maxim;++i)
		vx[i]+=vx[i-1];

	for(i=0;i<n;++i){
		if(nr[i].first>dx)
			sd+=nr[i].first-dx;
	}
	minim=sd;
	for(i=1;i<=maxim-dx;++i){
		ss+=vx[i-1];
		sd=sd-vx[maxim]+vx[i+dx-1];
		if(ss+sd<minim)
			minim=ss+sd;
	}
	suma=minim;
	
	for(i=1;i<=maxi;++i)
		vy[i]+=vy[i-1];
	
	ss=sd=0;
	for(i=0;i<n;++i){
		if(nr[i].second>dy)
			sd+=nr[i].second-dy;
	}
	minim=sd;
	for(i=1;i<=maxi-dy;++i){
		ss+=vy[i-1];
		sd=sd-vy[maxi]+vy[i+dy-1];
		if(ss+sd<minim)
			minim=sd+ss;
	}
	suma+=minim;
	printf("%d\n",suma);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}