Cod sursa(job #350695)

Utilizator katakunaCazacu Alexandru katakuna Data 25 septembrie 2009 15:07:54
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <cstdio>
#define Nmax 50100

int n, dx, dy, x, y,  i, mx, my, xmax, ymax;
int X[Nmax], Y[Nmax], Sx[Nmax], Sy[Nmax], Lx[Nmax], Ly[Nmax];

int main () {

	FILE *f = fopen ("tribute.in", "r");
	FILE *g = fopen ("tribute.out", "w");

	fscanf (f, "%d %d %d", &n, &dx, &dy);
	for (i = 1; i <= n; i++) {
		fscanf (f, "%d %d", &x, &y);
		X[x]++; Y[y]++;
		if (xmax < x) xmax = x;
		if (ymax < y) ymax = y;
	}
	
	Sx[0] = X[0];
	for (i = 1; i <= xmax; i++)
		Sx[i] = Sx[i-1] + X[i];

	Sy[0] = Y[0];
	for (i = 1; i <= ymax; i++)
		Sy[i] = Sy[i-1] + Y[i];
	
	/////////////////////////////////////
	for (i = dx+1; i <= xmax; i++)
		Lx[0]+= (i - dx) * X[i];
	
	mx = Lx[0];
	for (i = 1; i <= xmax - dx; i++) {
		Lx[i] = Lx[i-1] - ( Sx[xmax] - Sx[i+dx-1] ) + Sx[i-1];	
		if (mx > Lx[i]) mx = Lx[i];
	}

	////////////////////////////////////////
	for (i = dy+1; i <= ymax; i++)
		Ly[0]+= (i - dy) * Y[i];
	
	my = Ly[0];
	for (i = 1; i <= ymax - dy; i++) {
		Ly[i] = Ly[i-1] - ( Sy[ymax] - Sy[i+dy-1] ) + Sy[i-1];	
		if (my > Ly[i]) my = Ly[i];
	}
	
	fprintf (g, "%d", mx + my);
	
	fclose (f);
	fclose (g);
	
	return 0;

}