Cod sursa(job #181542)

Utilizator varuvasiTofan Vasile varuvasi Data 18 aprilie 2008 15:09:53
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 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));
	/*memset(s, 0, sizeof(s));
	memset(revs, 0, sizeof(revs));
	memset(sumL, 0, sizeof(sumL));
	memset(sumR, 0, sizeof(sumR));*/
	FOR(i, 1, N)
		count[pos[i]]++;
/*	FOR(i, 0, maxC)
		fprintf(fout, "%d ", count[i]);*/
//	fprintf(fout, "\n");
/*	s[0] = count[0];
	FOR(i, 1, maxC)
		s[i] = count[i] + s[i - 1];
	FORD(i, maxC, 0)
		revs[i] = count[i] + revs[i + 1];*/
	
	sump = count[0];
	FOR(i, 1, maxC)
	{
		sumL[i] = sumL[i - 1] + sump;
//		fprintf(fout, "%d ", sumL[i]);
		sump += count[i];
	}
//	fprintf(fout, "\n");
	sump = 0;
	FORD(i, maxC, 0)
	{
		sumR[i] = sumR[i + 1] + sump;
//		fprintf(fout, "%d ", sumR[i]);
		sump += count[i];
	}
//	fprintf(fout, "\n");

	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]);
	//	if (maxC < X[i]) maxC = X[i];
	//	if (maxC < Y[i]) maxC = Y[i];
	}
	//fprintf(fout, "%d\n", maxC);
	fprintf(fout, "%lld", go(X, DX) + go(Y, DY));
	fclose(fin), fclose(fout);
}