Cod sursa(job #481135)

Utilizator ooctavTuchila Octavian ooctav Data 30 august 2010 18:47:35
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

const int NMAX = 50050;
const int INF = 1000000000;

int N, Dx, Dy;
int Tx, Ty, Txb, Tyb;
int x[NMAX], y[NMAX];
int xmax = -1, ymax = -1;
int rez1, rez2;
int xex, yex;

void citire()
{
	cin >> N >> Dx >> Dy;
	for(int i = 1 ; i <= N ; i++)
	{
		cin >> x[i] >> y[i];
		xmax = max(xmax, x[i]);
		Tx += x[i];
		if(x[i] > Dx)
			xex += x[i] - Dx;
		ymax = max(ymax, y[i]);
		Ty += y[i];
		if(y[i] > Dy)
			yex += y[i] - Dy;
	}
}

void baleiere_x()
{
	int nrx[NMAX];
	int ind = 0;
	rez2 = xex;
	for(int i = 0 ; i <= xmax ; i++)
	{
		while(x[ind + 1] == i)
			ind++;
		nrx[i] = ind;
	}
	for(int i = 0 ; i < Dx ; i++)
		Tx -= (nrx[xmax] - nrx[i]);
	for(int i = 0 ; i <= xmax - Dx ; i++)
	{
		rez2 = min(rez2, Tx + Txb);
		Tx -= (nrx[xmax] - nrx[i + Dx]);
		Txb += nrx[i];
	}
}

void baleiere_y()
{
	int nry[NMAX];
	int ind = 0;
	rez1 = yex;
	for(int i = 0 ; i <= ymax ; i++)
	{
		while(y[ind + 1] == i)
			ind++;
		nry[i] = ind;
	}
	for(int i = 0 ; i < Dy ; i++)
		Ty -= (nry[ymax] - nry[i]);
	for(int i = 0 ; i <= ymax - Dy ; i++)
	{
		rez1 = min(rez1, Ty + Tyb);
		Ty -= (nry[ymax] - nry[i + Dy]);
		Tyb += nry[i];
	}
}

int main()
{
	freopen("tribute.in", "r", stdin);
	freopen("tribute.out", "w", stdout);
	citire();
	sort(x + 1, x + N + 1);
	sort(y + 1, y + N + 1);
	baleiere_x();
	baleiere_y();
	printf("%d\n", rez1 + rez2);
	return 0;
}