Cod sursa(job #1294547)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 17 decembrie 2014 19:52:32
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<fstream>
using namespace std;
int n, x, y, dx, dy, i, nrp, xmin, ymin;
int v[50001], w[50001], fx[50003], sx[50003], fy[50003], sy[50003];
ifstream fin("tribute.in");
ofstream fout("tribute.out");
int main(){
	fin>> n >> dx >> dy;
	for(i = 1; i <= n; i++){
		fin>> x >> y;
		v[x] = 1;
		w[y] = 1;
	}
	nrp = 0;
	if(v[0] == 1){
		nrp = 1;
	}
	for(i = 1; i <= 50000; i++){
		fx[i] = fx[i-1] + nrp;
		if(v[i] == 1){
			nrp++;
		}
	}
	nrp = 0;
	if(v[50000] == 1){
		nrp = 1;
	}
	for(i = 49999; i >= 0; i--){
		sx[i] = sx[i+1] + nrp;
		if(v[i] == 1){
			nrp++;
		}
	}
	nrp = 0;
	if(w[0] == 1){
		nrp = 1;
	}
	for(i = 1; i <= 50000; i++){
		fy[i] = fy[i-1] + nrp;
		if(w[i] == 1){
			nrp++;
		}
	}
	nrp = 0;
	if(w[50000] == 1){
		nrp = 1;
	}
	for(i = 49999; i >= 0; i--){
		sy[i] = sy[i+1] + nrp;
		if(w[i] == 1){
			nrp++;
		}
	}
	xmin = sx[dx-1];
	for(i = 1; i <= 50000 - dx+1; i++){
		if(fx[i] + sx[i + dx - 1] < xmin){
			xmin = fx[i] + sx[i + dx - 1];
		}
	}
	ymin = sy[dy-1];
	for(i = 1; i <= 50000 - dy+1; i++){
		if(fy[i] + sy[i + dy- 1] < ymin){
			ymin = fy[i] + sy[i + dy - 1];
		}
	}
	fout<< xmin + ymin;
	return 0;
}