Cod sursa(job #110197)

Utilizator raula_sanChis Raoul raula_san Data 25 noiembrie 2007 20:22:00
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstdio>
#include <vector>

#define dim 50001

using namespace std;

int N;
int S;
int Dx, Dy;
int Mx, My;

int Cx[dim], Cy[dim];

vector < pair <int, int> > V;

void read()
{
	freopen("tribute.in", "rt", stdin);
	
	int i, x, y;
	
	for(scanf("%d %d %d", &N, &Dx, &Dy), i=1; i<=N; ++i)
	{
		scanf("%d %d", &x, &y);
		V.push_back(make_pair(x, y));
	
		Mx = x > Mx ? x : Mx;
		My = y > My ? y : My;
	
		++ Cx[x];
		++ Cy[y];
	}
	
	fclose(stdin);
}

void solve()
{
	int i, s, st, dr, dx, dy;
	
	for(i=s=dr=0; i<N; ++i)
		if(V[i].first > Dx)
		{
			s += V[i].first - Dx;
			++ dr;
		}
	
	dx = s;
	st = 0;
			
	for(i=1; i<=Mx-Dx; ++i)
	{
		st += Cx[i-1];
		dr -= Cx[i+Dx-1];
		
		s += st;
		s -= dr;
		
		dx = s < dx ? s : dx;
	}
	
	for(i=s=dr=0; i<N; ++i)
		if(V[i].second > Dy)
		{
			s += V[i].second - Dy;
			++ dr;
		}
		
	dy = s;
	st = 0;
	
	for(i=0; i<=My-Dy; ++i)
	{
		st += Cy[i-1];
		dr -= Cy[i+Dy-1];
		
		s += st;
		s -= dr;
		
		dy = s < dy ? s : dy;
	}
	
	S = dx + dy;
}

void write()
{
	freopen("tribute.out", "wt", stdout);
	
	printf("%d", S);
	
	fclose(stdout);
}

int main()
{
	read();
	solve();
	write();
	
	return 0;
}