Cod sursa(job #716769)

Utilizator CS-meStanca Marian Ciprian CS-me Data 19 martie 2012 11:14:20
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<stdio.h>
#include<string.h>
FILE *fin=fopen("tribute.in","r");
FILE *fout=fopen("tribute.out","w");

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

int main(){
	
	fscanf(fin,"%d %d %d",&n,&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<=maxx;i++){
		ox=ox+fx[i];
		
		s[i]=s[i-1]+ox;
	}
	
	ox=fx[maxx];
	d[maxx]=0;
	
	for(i=maxx-1;i>=0;i--){
		ox=ox+fx[i];
		
		d[i]=d[i+1]+ox;
	}
	min = d[dx];
	pozminx = 0;
	for(i=1;i<=maxx-dx;i++){
		if(min > s[i-1] + d[i+dx]){
			min = s[i-1] + d[i+dx];
			pozminx = i;
		}
	}
	
	suma+=min;
	
	memset(s,0,sizeof(s));
	memset(d,0,sizeof(d));
	
	
	oy=fy[0];
	s[0]=oy;
	for(i=1;i<=maxy;i++){
		oy=oy+fy[i];
		
		s[i]=s[i-1]+oy;
	}
	
	oy=fy[maxx];
	d[maxx]=oy;
	
	for(i=maxy-1;i>=0;i--){
		oy=oy+fy[i];
		
		d[i]=d[i+1]+oy;
	}
	min = d[dy];
	pozminy = 0;
	for(i=1;i<=maxy-dy+1;i++){
		if(min > s[i-1] + d[i+dy]){
			min = s[i-1] + d[i+dy];
			pozminy = i;
		}
	}
	
	suma+=min;

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