Cod sursa(job #2461695)

Utilizator aurelionutAurel Popa aurelionut Data 25 septembrie 2019 23:06:58
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int INF = (1 << 30);
const int NMAX = 50005;
int n, dx, dy;
long long X[NMAX], Y[NMAX];

int main()
{
	ifstream fin("tribute.in");
	ofstream fout("tribute.out");
	fin >> n >> dx >> dy;
	for (int i = 1;i <= n;++i)
	{
		int x, y;
		fin >> x >> y;
		++X[x];
		++Y[y];
	}
	long long cntleft, cntright, mnx, mny, sumleft, sumright;
	cntleft = 0, cntright = n, sumleft = 0, sumright = 0;
	for (int i = 0;i <= 50000;++i)
		sumright += 1LL * X[i] * i;
	mnx = sumright;
	sumright += n;
	for (int i = 0;i <= 50000;++i)
	{
		if (i - dx - 1 >= 0)
		{
			cntleft += X[i - dx - 1];
			sumleft += cntleft;
		}
		sumright -= cntright;
		cntright -= X[i];
		mnx = min(mnx, sumleft + sumright);
	}
	cntleft = 0, cntright = n, sumleft = 0, sumright = 0;
	for (int i = 0;i <= 50000;++i)
		sumright += 1LL * Y[i] * i;
	mny = sumright;
	sumright += n;
	for (int i = 0;i <= 50000;++i)
	{
		if (i - dy - 1 >= 0)
		{
			cntleft += Y[i - dy - 1];
			sumleft += cntleft;
		}
		sumright -= cntright;
		cntright -= Y[i];
		mny = min(mny, sumleft + sumright);
	}
	fout << mnx + mny << "\n";
	fin.close();
	fout.close();
	return 0;
}