Cod sursa(job #332959)

Utilizator marinMari n marin Data 21 iulie 2009 08:01:52
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <stdio.h>

#define DIM 100010
#define INF 4000000000LL

int AX[DIM],AY[DIM],BX[DIM],BY[DIM];

long long SX[DIM],SY[DIM],TX[DIM],TY[DIM],mx,my;

int i,maxx,maxy,x,y,n,dx,dy;

int main(){
	FILE *f = fopen("tribute.in","r");
	fscanf(f,"%d %d %d",&n, &dx, &dy);
	for (i=1;i<=n;i++) {
		fscanf(f,"%d %d",&x, &y);
		AX[x]++;
		AY[y]++;
		if (x>maxx)
			maxx = x;
		if (y>maxy)
			maxy = y;
	}
	fclose(f);
	
	BX[0] = AX[0];
	BY[0] = AY[0];
	for (i=1;i<=maxx;i++)
		BX[i] = BX[i-1] + AX[i];
	for (i=1;i<=maxy;i++)
		BY[i] = BY[i-1] + AY[i];
	
	SX[0] = 0;
	for (i=1;i<=maxx;i++)
		SX[i] = SX[i-1]+BX[i-1];
	SY[0] = 0;
	for (i=1;i<=maxy;i++)
		SY[i] = SY[i-1]+BY[i-1];
	
	TX[maxx] = 0;
	for (i=maxx-1;i>=0;i--)
		TX[i] = TX[i+1] + BX[maxx] - BX[i];
	TY[maxy] = 0;
	for (i=maxy-1;i>=0;i--)
		TY[i] = TY[i+1] + BY[maxy] - BY[i];
	
	mx = INF;
	for (i=0;i<=maxx;i++)
		if (SX[i]+TX[i+dx]<mx)
			mx = SX[i]+TX[i+dx];
	my = INF;
	for (i=0;i<=maxy;i++)
		if (SY[i]+TY[i+dy]<my)
			my = SY[i]+TY[i+dy];
		
	FILE *g = fopen("tribute.out","w");
	fprintf(g,"%lld",mx+my);
	fclose(g);
		
	return 0;
}