Cod sursa(job #892877)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 26 februarie 2013 12:02:21
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
using namespace std;
ifstream fin ("tribute.in");
ofstream fout("tribute.out");

long long xi[500005] , yi[500005], a,b,x,y,n,maxim,maxim1,minim,minim1,i,s;
long long CS[500005] , CD[500005];


int main () {
	
	fin>>n>>x>>y;
	for (i=1;i<=n;i++) {
		fin>>a>>b; 

		if (a>maxim) 
			maxim=a;
		if (b>maxim1) 
			maxim1=b;

		xi[a]++;
		yi[b]++;
	}

	CS[0] = 0;
	
	for (i=1;i<=maxim;i++) {
		CS[i] = CS[i-1] + xi[i-1];
		xi[i] += xi[i-1];
	}
	
	minim=200000000000000LL;
	minim1=200000000000000LL;
	
	CD[maxim] = 0;
	for (i=maxim-1;i>=0;i--) {
		CD[i] = CD[i+1] + (xi[maxim] - xi[i]);
	}
	
	for (i=0;i+x <= maxim;i++) {
		if (CS[i] + CD[i+x] < minim)
			minim = CS[i] + CD[i+x];
	}
	
	CS[0] = 0;
	
	for (i=1;i<=maxim1;i++) {
		CS[i] = CS[i-1] + yi[i-1];
		yi[i] += yi[i-1];
	}
	
	CD[maxim1] = 0;
	for (i=maxim1-1;i>=0;i--) {
		CD[i] = CD[i+1] + (yi[maxim1] - yi[i]);
	}
	
	for (i=0;i+y <= maxim1;i++) {
		if (CS[i] + CD[i+y] < minim1)
			minim1 = CS[i] + CD[i+y];
	}
	
	
	
	fout<<minim+minim1<<"\n";

	return 0; 
}