Cod sursa(job #600624)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 2 iulie 2011 17:26:53
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<stdio.h>
int dx,dy,nrx[50010],nry[50010],s[50010],ss[50010],n,d,k,min,sum,min2;

int main()
{
	int a,b,i;
	freopen("tribute.in","r",stdin);
	freopen("tribute.out","w",stdout);
	scanf("%d%d%d",&n,&dx,&dy);
	for(i=1;i<=n;++i)
	{
		scanf("%d %d",&a,&b);
		nrx[a]++;
		nry[b]++;
	}
	s[0]=nrx[0];
	ss[0]=nry[0];
	for(i=1;i<=50000;++i)
	{
		s[i] = s[i-1] +nrx[i];
		ss[i] = ss[i-1] + nry[i];
	}
	for(i=dx+1 ; i<=50000 ; i++)
		d += (i-dx)*nrx[i];
	min=d;
	k=50000-dx+1;
	//printf("0: min = %d\n",d);
	for(i=1;i<=k;++i)
	{
		d += s[i-1];
		d -= s[50000]-s[i+dx-1]; 
		if(d<min)
		{
			min=d;
//			printf("%d: min = %d\n",i,min);
		}
	}
	//printf("%d",min);
	min2=min;
	
	d=0;
	for(i=dy+1 ; i<=50000 ; i++)
		d += (i-dy)*nry[i];
	min=d;
	k=50000-dy+1;
//	printf("0: min = %d\n",d);
	for(i=1;i<=k;++i)
	{
		d += ss[i-1];
		d -= ss[50000]-ss[i+dy-1]; 
		if(d<min)
		{
			min=d;
		//	printf("%d: min = %d\n",i,min);
		}
	}
	printf("%d",min2+min);
	
	
}