Cod sursa(job #1141837)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 13 martie 2014 10:47:09
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <algorithm>
using namespace std;
int n, DX, DY, X[50100], Y[50100];
long long sol1, sol2;

int main()
{
	int i, st, dr;
	long long now;
	ifstream fin("tribute.in");
	fin >> n >> DX >> DY;
	for(i = 1; i <= n; ++i)
		fin >> X[i] >> Y[i];
	fin.close();
	
	sort(X + 1, X + n + 1);
	sort(Y + 1, Y + n + 1);
	
	// pentru DX
	st = 0;
	dr = n + 1;
	now = 0;
	for(i = n; i > 0; --i)
		if(X[i] > DX)
		{
			now += X[i] - DX;
			dr = i;
		}
	sol1 = now;
	for(i = 1; i + DX <= 50000; ++i)
	{
		while(st + 1 <= n && X[st + 1] < i)
			st++;
		while(dr <= n && X[dr] <= i + DX)
		{
			now--;
			dr++;
		}
		now += st;
		now -= (n - dr + 1);
		sol1 = min(sol1, now);
	}
	// pentru DY
	st = 0;
	dr = n + 1;
	now = 0;
	for(i = n; i > 0; --i)
		if(Y[i] > DY)
		{
			now += Y[i] - DY;
			dr = i;
		}
	sol2 = now;
	for(i = 1; i + DY <= 50000; ++i)
	{
		while(st + 1 <= n && Y[st + 1] < i)
			st++;
		while(dr <= n && Y[dr] <= i + DY)
		{
			now--;
			dr++;
		}
		now += st;
		now -= (n - dr + 1);
		sol2 = min(sol2, now);
	}
	
	ofstream fout("tribute.out");
	fout << (sol1 + sol2) << "\n";
	fout.close();
	return 0;
}