Cod sursa(job #667552)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 23 ianuarie 2012 13:02:48
Problema Tribute Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<fstream>

using namespace std;

ifstream f("tribute.in");
ofstream g("tribute.out");

long long i,j,n,dx,dy,x[50009],y[50009];
long long  nrd,sumd,dr,nrst,st,sumst,minx=5000009,miny=5000009,maxx,maxy;

int max(int a,int b)
{
	if(a>b) return a;
	return b;
}

int min(int a,int b)
{
	if(a<b) return a;
	return b;
}

int main()
{
	f>>n>>dx>>dy;
	
	for(i=1;i<=n;++i)
	{
		int a,b;
		f>>a>>b;
		x[a]++;
		y[b]++;
		if(a>=dx) 
		{
			sumd+=a;
			nrd++;
		}
		maxx=max(maxx,a);
		maxy=max(maxy,b);
	}
	
	nrst=0;
	sumst=0;
	
	for(st=0,dr=dx;dr<=maxx+1;st++,dr++)
	{
		minx=min(minx,sumd-(nrd*dr)+ (st*nrst)-sumst);
		nrst+=x[st];
		sumst+=(st*x[st]);
		
		nrd-=x[dr];
		sumd-=((dr)*x[dr]);
	}
	
	nrst=0;
	sumst=0;
	nrd=0;
	sumd=0;
	
	for(i=dy;i<=maxy+1;++i) 
	{	
		nrd+=y[i];
		sumd+=(y[i]*i);
	}
	
	for(st=0,dr=dy;dr<=maxy+1;st++,dr++)
	{
		miny=min(miny,sumd-(nrd*dr)+ (st*nrst)-sumst);
		nrst+=y[st];
		sumst+=(st*y[st]);
		
		nrd-=y[dr];
		sumd-=((dr)*y[dr]);
	}
	
	minx+=miny;
	
	g<<minx;
	
	f.close();
	g.close();
	
	return 0;
}