Cod sursa(job #194112)

Utilizator swift90Ionut Bogdanescu swift90 Data 8 iunie 2008 14:12:06
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 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,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);
	sort(nr,nr+n);
	ss=sd=0;
	for(i=0;i<n;++i){
		if(nr[i].first>dx)
			sd+=nr[i].first-dx;
		
		++vx[nr[i].first];
		++vy[nr[i].second];
		if(nr[i].second>maxi)
			maxi=nr[i].second;
	}
	maxim=nr[n-1].first;
	for(i=1;i<=maxim;++i)
		vx[i]+=vx[i-1];
	
	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;
}