Cod sursa(job #1294304)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 17 decembrie 2014 11:30:42
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++){
		sx[i] = sx[i-1] + nrp;
		if(v[i] == 1){
			nrp++;
		}
	}
	nrp = 0;
	if(v[50000] == 1){
		nrp = 1;
	}
	for(i = 49999; i >= 0; i--){
		fx[i] = fx[i+1] + nrp;
		if(v[i] == 1){
			nrp++;
		}
	}
	nrp = 0;
	if(w[0] == 1){
		nrp = 1;
	}
	for(i = 1; i <= 50000; i++){
		sy[i] = sy[i-1] + nrp;
		if(w[i] == 1){
			nrp++;
		}
	}
	nrp = 0;
	if(w[50000] == 1){
		nrp = 1;
	}
	for(i = 49999; i >= 0; i--){
		fy[i] = fy[i+1] + nrp;
		if(w[i] == 1){
			nrp++;
		}
	}
	xmin = fx[dx-1];
	for(i = 1; i <= 50000 - dx+1; i++){
		if(sx[i] + fx[i + dx - 1] < xmin){
			xmin = sx[i] + fx[i + dx - 1];
		}
	}
	ymin = fy[dy-1];
	for(i = 1; i <= 50000 - dy+1; i++){
		if(sy[i] + fy[i + dy- 1] < ymin){
			ymin = sy[i] + fy[i + dy - 1];
		}
	}
	fout<< xmin + ymin;
	return 0;
}