Cod sursa(job #32240)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 17 martie 2007 16:32:29
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
# include <stdio.h>

const int MAXCOORD=50000; //AICI!!!! 50,000

long int maxx,maxy,freq_x[MAXCOORD+1],freq_y[MAXCOORD+1],dx,dy,n;

long int dmin(long int span, long int freq[],long int cmax)
{
long int min=0,prim=0,drta=0,stga=0,sdrta,sstga=0,i;
for (i=span+1;i<=cmax;i++)
	{
	drta+=freq[i];
	min+=freq[i]*(i-span);
	}
sdrta=min;
while (prim<cmax-span)
	{
	prim++;
	stga+=freq[prim-1];
	sstga+=stga;
	sdrta-=drta;
	drta-=freq[prim+span];
	if (sstga+sdrta<min) min=sstga+sdrta;
	}
return min;
}

void citire()
{
long int aa,bb;
FILE *f=fopen("tribute.in","r");
fscanf(f,"%ld%ld%ld",&n,&dx,&dy);
for (long int i=1;i<=n;i++)
	{
	fscanf(f,"%ld%ld",&aa,&bb);
	if (i==1) {maxx=aa;maxy=bb;}
	else
		{
		if (aa>maxx) maxx=aa;
		if (bb>maxy) maxy=bb;
		}
	freq_x[aa]++;
	freq_y[bb]++;
	}
fclose(f);
}

void scrie()
{
FILE *g=fopen("tribute.out","w");
fprintf(g,"%ld\n",dmin(dx,freq_x,maxx)+dmin(dy,freq_y,maxy));
fcloseall();
}

int main()
{
citire();
scrie();
return 0;
}