Cod sursa(job #2988160)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 3 martie 2023 18:23:25
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
//Ilie Dumitru
#include<cstdio>
#include<algorithm>
const int NMAX=50005;
//pot scrie ll in loc de long long int
typedef long long int ll;

int x[NMAX], y[NMAX];

ll solve(int* v, int d)
{
	int i;
	ll sum=0, trecute=0, viitoare=0, min;

	for(i=d+1;i<NMAX;++i)
	{
		sum+=v[i]*(ll)(i-d);
		viitoare+=v[i];
	}

	min=sum;
	for(i=0;i+d+1<NMAX;++i)
	{
		trecute+=v[i];
		sum+=trecute-viitoare;
		viitoare-=v[i+d+1];
		if(sum<min)
			min=sum;
	}

	return min;
}

int main()
{
	FILE* f=fopen("tribute.in", "r"), *g=fopen("tribute.out", "w");
	int i, N, a, b, dx, dy;

	fscanf(f, "%d%d%d", &N, &dx, &dy);
	for(i=0;i<N;++i)
	{
		fscanf(f, "%d%d", &a, &b);
		++x[a];
		++y[b];
	}

	fprintf(g, "%lld", solve(x, dx)+solve(y, dy));

	fclose(f);
	fclose(g);
	return 0;
}