Cod sursa(job #599836)

Utilizator rumburakrumburak rumburak Data 29 iunie 2011 18:18:14
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>

using namespace std;

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

const int N = 50008;

int n, dx, dy, nrx[N], nry[N], sumx[N], sumy[N];

void citire()
{
	int x, y;
	in>>n>>dx>>dy;
	for(int i=1; i<=n; i++)
	{
		in>>x>>y;
		++nrx[x];
		++nry[y];
	}
}

void sumep(int nr[N], int sum[N])
{
	sum[0] = nr[0];
	for(int i=1; i<N; i++)
		sum[i] = sum[i-1] + nr[i];
}

long long rez(int nr[N], int sum[N], int d)
{
	int i;
	long long sc = 0, smin;
	for(i=1+d; i<N; i++)
		sc += (long long)(i-d)*nr[i];
	smin = sc;
	for(i=1; i<N-d; i++)
	{
		sc += sum[i-1] - (sum[N-1] - sum[i+d-1]);
		if(sc < smin)
			smin = sc;
	}
	return smin;
}

int main()
{
	citire();
	sumep(nrx, sumx);
	sumep(nry, sumy);
	out<<rez(nrx, sumx, dx) + rez(nry, sumy, dy);
	return 0;
}