Cod sursa(job #31247)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 15 martie 2007 18:27:42
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<stdio.h>
long long int n,dx,dy,a,b,i,x[50001],y[50001],l,s[50001],xmax,ymax,j,m,solx,p,sc,soly,sol;
int main()
{
	FILE *f,*g;
	f=fopen("tribute.in","r");
	g=fopen("tribute.out","w");
	fscanf(f,"%lld%lld%lld",&n,&dx,&dy);
	xmax=0;ymax=0;
	for(i=1;i<=n;i++)
	{fscanf(f,"%lld%lld",&a,&b);
	 x[a]=x[a]+1;y[b]=y[b]+1;
	 if(a>xmax)xmax=a;if(b>ymax)ymax=b;
	}
	l=xmax;
	s[0]=x[0];
	for(i=1;i<=l;i++)
	{s[i]=s[i-1]+x[i];}
	m=dx;
	for(j=m;j<=l;j++)
	solx=solx+s[l]-s[j];
	sc=solx;
	for(p=0;p<=l-m;p++)
	{sc=sc-s[l]+s[p]+s[m+p];
	if(sc<solx)solx=sc;
	}
	l=ymax;
	s[0]=y[0];
	for(i=1;i<=l;i++)
	{s[i]=s[i-1]+y[i];}
	m=dy;
	for(j=m;j<=l;j++)
	soly=soly+s[l]-s[j];
	sc=soly;
	for(p=0;p<=l-m;p++)
	{sc=sc-s[l]+s[p]+s[m+p];
	if(sc<solx)solx=sc;
	}
	sol=solx+soly;
	fprintf(g,"%lld\n",sol);
	fcloseall();
	return 0;
}