Cod sursa(job #644220)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 5 decembrie 2011 17:08:25
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <stdlib.h>
using namespace std;

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

const long long dim = 50005;
long long S[dim], D[dim], X[dim], Y[dim], DX, DY, N;

long long minim (long long a, long long b)
{
	return a < b ? a : b;
}

long long cauta (long long A[], long long DD)
{
	long long nr, m = dim * dim;
	
	S[0] = 0;
	nr = A[0];
	for (int i = 1; i < dim; i++)
	{
		S[i] = S[i-1] + nr;
		nr += A[i];
	}
	
	nr = 0;
	for (int i = dim - 2; i >= 0; i--)
	{
		D[i] = D[i+1] + nr;
		nr += A[i];
	}
	
	for (int i = 0; i < dim-DD; i++)
		m = minim (abs (S[i] + D[i+DD-1]), m);
	return m;
}

int main ()
{
	fi >> N >> DX >> DY;
	DX++; DY++;
	for (int i = 1, x, y; i <= N; i++)
	{
		fi >> x >> y;
		X[x]++; Y[y]++; 
	}
	fo << cauta (X, DX) + cauta (Y, DY);
	return 0;
}