Cod sursa(job #716834)

Utilizator CS-meStanca Marian Ciprian CS-me Data 19 martie 2012 12:15:35
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<stdio.h>
#include<string.h>

#define DIM 50005

FILE *fin=fopen("tribute.in","r");
FILE *fout=fopen("tribute.out","w");

int n,dx,dy,ox,oy,maxx,maxy,pozminx,pozminy,i,x,y;
int fx[50010],fy[50010];
long long s[50010];
long long d[50010];
long long suma,min;

int main(){
	
	fscanf(fin,"%d %d %d",&n,&dx,&dy);
	dx++;
	dy++;
	
	for(i=1;i<=n;i++){
		fscanf(fin,"%d %d",&x,&y);
		
		fx[x]++;
		fy[y]++;
		
		if(x > maxx){
			maxx = x;
		}
		if(y > maxy){
			maxy = y;
		}
	}
	
	ox=fx[0];
	s[0]=0;
	for(i=1;i<DIM;i++){
		s[i]=s[i-1]+(long long)ox;
		ox+=fx[i];
	}
	
	ox=0;
	d[DIM]=0;
	
	for(i=DIM-2;i>=0;i--){		
		d[i]=d[i+1]+(long long)ox;
		ox+=fx[i];
	}
	min = ((long long)DIM)*DIM;
	for(i=0;i<DIM-dx;i++){
		if(min > s[i] + d[i+dx-1]){
			min = s[i] + d[i+dx-1];
		}
	}
	
	suma+=min;
	
	memset(s,0,sizeof(s));
	memset(d,0,sizeof(d));
	
	
	oy=fy[0];
	for(i=1;i<=DIM-1;i++){		
		s[i]=s[i-1]+(long long)oy;
		oy+=fy[i];
	}
	
	oy=0;	
	for(i=DIM-2;i>=0;i--){
		d[i]=d[i+1]+(long long)oy;
		oy+=fy[i];
	}
	min = ((long long)DIM) * DIM;
	for(i=0;i<DIM-dy;i++){
		if(min > s[i] + d[i+dy-1]){
			min = s[i] + d[i+dy-1];
		}
	}
	
	suma+=min;

	fprintf(fout,"%lld",suma);
	
	return 0;
}