Cod sursa(job #600623)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 2 iulie 2011 17:26:44
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<iostream>
#include<fstream>
#define N 50001
using namespace std;

ifstream in("tribute.in");
ofstream out("tribute.out");

int n,dx,dy,x[N][2],vx[N],vy[N],distmax=N,nrmax,dist,dist2,distmax2=N;

int main() {
	int i,w;
	
	in >> n >> dx >> dy;
	
	for(i=1;i<=n;++i) {
		in >> x[i][0] >> x[i][1];
		
		if(x[i][0]==0)
			++dist;
		
		if(x[i][1]==0)
			++dist2;
		
		if(x[i][0]>dx+1)
			dist+=x[i][0]-dx-1;
		if(x[i][1]>dy+1)
			dist2+=x[i][1]-dy-1;
		
		vx[x[i][0]]++;
		vy[x[i][1]]++;
	}
	
	for(i=1;i<N;++i) {
		vx[i]+=vx[i-1];
		vy[i]+=vy[i-1];
	}
	
	w=N-dx; distmax=dist;
	
	for(i=2;i<=w;++i) {
		
		dist+=vx[i-1] - vx[N-1] + vx[i+dx-1];
		
		if(dist<distmax) {
			distmax=dist;
			nrmax=i;
		}
	}
	
	w+=dx-dy; distmax2=dist2;
	
	for(i=2;i<=w;++i) {
		
		dist2+=vy[i-1] - vy[N-1] + vy[i+dy-1];
		
		if(dist2<distmax2)
			distmax2=dist2;
	}
	
	out << distmax+distmax2;
	
	return 0;
}