Cod sursa(job #600626)

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

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

int n,dx,dy,a,b,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 >> a >> b;
		
		if(a>dx+1)
			dist+=a-dx;
		if(b>dy+1)
			dist2+=b-dy;
		
		vx[a]++;
		vy[b]++;
	}
	
	for(i=1;i<N;++i) {
		vx[i]+=vx[i-1];
		vy[i]+=vy[i-1];
	}
	
	w=N-dx; distmax=dist;
	
	for(i=1;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=1;i<=w;++i) {
		
		dist2+=vy[i-1] - vy[N-1] + vy[i+dy-1];
		
		if(dist2<distmax2)
			distmax2=dist2;
	}
	
	out << distmax+distmax2;
	
	return 0;
}