Cod sursa(job #2298027)

Utilizator AlexPascu007Pascu Ionut Alexandru AlexPascu007 Data 6 decembrie 2018 23:19:14
Problema Tribute Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#define inf 200000000
#define Ox first
#define Oy second
using namespace std;
ifstream fin("tribute.in");
ofstream fout("tribute.out");
long long n,dx,dy,f[50010],s[50010],d[50010],ps[50010],pd[50010],minim[5],t,poz,i,ans;
pair<long long,long long> p[50010];
int main() {
	fin>>n>>dx>>dy;
	for (i=1;i<=n;i++)
		fin>>p[i].Ox>>p[i].Oy;
	for (t=1;t<=2;t++) {
		for (i=0;i<=50000;i++)
			f[i]=0;
		for (i=1;i<=n;i++) {
			if (t==1)
				f[p[i].Ox]++;
			else
				f[p[i].Oy]++;
		}
		//proiectez coordonatele punctelor pe axa Ox si Oy, pe rand
		s[0]=0; ps[0]=f[0]; //initializez suma din stanga si nr punctelor din stanga
		for (i=1;i<=50000;i++) {
			s[i]=s[i-1]+ps[i-1];
			ps[i]=ps[i-1]+f[i];
		}
		d[50000]=0; pd[50000]=f[50000]; //initializez suma din dreapta si nr punctelor din dreapta
		for (i=49999;i>=0;i--) {
			d[i]=d[i+1]+pd[i+1];
			pd[i]=pd[i+1]+f[i];
		}
		minim[t]=inf;
		for (poz=0;poz+dx<=50000;poz++)
			minim[t]=min(minim[t],s[poz]+d[poz+dx]);
		dx=dy; //"schimb" axa Ox cu Oy
		ans+=minim[t];
	}
	fout<<ans;
	return 0;
}