Cod sursa(job #1261160)

Utilizator EpictetStamatin Cristian Epictet Data 11 noiembrie 2014 23:49:48
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("tribute.in");
ofstream fout ("tribute.out");
int N, dx, dy, x, y, sol, minx, maxx, miny, maxy, OX[50010], OY[50010];

int Det_Dist_Min(int V[], int d, int st, int dr)
{
	int sum = 0;
	for (int i=st+d; i<=dr; i++)
	{
		sum += (i - (st + d)) * V[i]; 
	}
	int minim = sum;
	for (int i=st+1; i<=dr; i++)
	{
		V[i] += V[i-1];
	}
	for (int i=st+1; i<=dr-d; i++)
	{
		sum += V[i-1];
		sum -= N;
		sum += V[i-d+1];
		if (sum < minim) minim = sum;
	}
	return minim;
}

int main()
{
	fin >> N >> dx >> dy;
	for (int i=1; i<=N; i++)
	{
		fin >> x >> y;
		if (x < minx) minx = x;
		if (x > maxx) maxx = x;
		if (y < miny) miny = y;
		if (y > maxy) maxy = y;
		OX[x]++;
		OY[y]++;
	}
	
	sol += Det_Dist_Min(OX, dx, minx, maxx);
	sol += Det_Dist_Min(OY, dy, miny, maxy);
	
	fout << sol << '\n';
	fout.close();
	return 0;
}