Cod sursa(job #1294563)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 17 decembrie 2014 20:12:52
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<fstream>
using namespace std;
int n, i, x, y, xmin, ymin, dx, dy, nrp;
int v[50001], w[50001], fx[50003], fy[50003], sx[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 = v[50000];
	for(i = 49999; i >= 0; i--){
		fx[i] = fx[i+1] + nrp;
		nrp += v[i];
	}
	nrp = w[50000];
	for(i = 49999; i >= 0; i--){
		fy[i] = fy[i+1] + nrp;
		nrp += w[i];
	}
	nrp = v[0];
	for(i = 1; i <= 50000; i++){
		sx[i] = sx[i-1] + nrp;
		nrp += v[i];
	}
	nrp = w[0];
	for(i = 1; i <= 50000; i++){
		sy[i] = sy[i-1] + nrp;
		nrp += w[i];
	}
	xmin = fx[dx-1];
	for(i = 1; i <= 50000-dx + 1; i++){
		if(xmin > fx[i+dx-1] + sx[i]){
			xmin = fx[i+dx-1] + sx[i];
		}
	}
	ymin = fy[dy-1];
	for(i = 1; i <= 50000-dy + 1; i++){
		if(ymin > fy[i+dy-1] + sy[i]){
			ymin = fy[i+dy-1] + sy[i];
		}
	}
	fout<< xmin + ymin;
	return 0;
}