Cod sursa(job #2605333)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 24 aprilie 2020 19:23:16
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
//#include <iostream>
#include <fstream>
#include <climits>

using namespace std;

ifstream cin("tribute.in");
ofstream cout("tribute.out");

const int NMAX = 50000;

int N, dx, dy;
int vfx[NMAX + 5], vfy[NMAX + 5], nrx, nry;

long long spl[NMAX + 5], spr[NMAX + 5], spu[NMAX + 5], spd[NMAX + 5];

int main()
{
	cin >> N >> dx >> dy;

	for(int i = 1; i <= N; i++)
	{
		int x, y; cin >> x >> y;
		vfx[x]++; vfy[y]++;
	}

	spl[0] = 0; nrx = vfx[0];
	for(int i = 1; i <= NMAX; i++)
		{
			spl[i] = spl[i - 1] + 1LL * nrx;
			nrx += vfx[i];
		}

	spr[NMAX] = 0; nrx = vfx[NMAX];
	for(int i = NMAX - 1; i >= 0; i--)
		{
			spr[i] = spr[i + 1] + 1LL * nrx;
			nrx += vfx[i];
		}

	spu[0] = 0; nry = vfy[0];
	for(int i = 1; i <= NMAX; i++)
		{
			spu[i] = spu[i - 1] + 1LL * nry;
			nry += vfy[i];
		}

	spd[NMAX] = 0; nry = vfy[NMAX];
	for(int i = NMAX - 1; i >= 0; i--)
		{
			spd[i] = spd[i + 1] + 1LL * nry;
			nry += vfy[i];
		}

	long long minSolX = LLONG_MAX, minSolY = LLONG_MAX;

	for(int i = 0; i <= NMAX - dx; i++)
		minSolX = min(minSolX, spl[i] + spr[i + dx]);

	for(int i = 0; i <= NMAX - dy; i++)
		minSolY = min(minSolY, spu[i] + spd[i + dy]);

	cout << minSolX + minSolY << '\n';

	return 0;
}