Cod sursa(job #181543)

Utilizator varuvasiTofan Vasile varuvasi Data 18 aprilie 2008 15:10:46
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#include <string.h>
#define maxn 60001
#define FOR(i, a, b) for (i = (a); i <= (b); i++)
#define FORD(i, a, b) for (i = (a); i >= (b); i--)

int N, DX, DY, maxC = 50000;
long long count[maxn], sumL[maxn], sumR[maxn];
int X[maxn], Y[maxn];
FILE *fin = fopen("tribute.in", "rt"), *fout = fopen("tribute.out", "wt");
long long go(int pos[maxn], int D)
{
	long long min_val = 1e14, i, sump;
	memset(count, 0, sizeof(count));
	FOR(i, 1, N)
		count[pos[i]]++;
	
	sump = count[0];
	FOR(i, 1, maxC)
	{
		sumL[i] = sumL[i - 1] + sump;
		sump += count[i];
	}
	sump = 0;
	FORD(i, maxC, 0)
	{
		sumR[i] = sumR[i + 1] + sump;
		sump += count[i];
	}

	FOR(i, 0, maxC - D)
		if (sumL[i] + sumR[i + D] < min_val)
			min_val = sumL[i] + sumR[i + D];

	return min_val;		
}

int main()
{
	int i;

	fscanf(fin, "%d %d %d", &N, &DX, &DY);
	FOR(i, 1, N)
	{
		fscanf(fin, "%d %d", &X[i], &Y[i]);
	}
	fprintf(fout, "%lld", go(X, DX) + go(Y, DY));
	fclose(fin), fclose(fout);
}