Cod sursa(job #994093)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 4 septembrie 2013 22:09:00
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<string.h>
using namespace std;

#define NMAX 50001
#define INF 1<<30

int x[NMAX],y[NMAX],s[NMAX],isdr[NMAX],isinside[NMAX];

int solve(int v[], int n, int d)
{
	int i,sum,min,st,dr;
	sum=0;
	dr=st=0;
	sort(v+1,v+n+1);
	memset(isdr,0,sizeof(isdr));
	memset(isinside,0,sizeof(isinside));
	for(i=1;i<=n;i++) 
		if(v[i]>d) {
			sum=sum+v[i]-d;
			dr++;
			isdr[v[i]]++;
		}
		else isinside[v[i]]++;
	min=sum;
	for(i=1;i<=v[n];i++) {
		if(isinside[i-1]) 
			st=st+isinside[i-1];
		sum=sum-dr;
		if(i+d<=NMAX-1) {
			if(isdr[i+d]) {
				dr=dr-isdr[i+d];
				isinside[i+d]=isinside[i+d]+isdr[i+d];
			}
		}
		sum=sum+st;
		if(sum<min)
			min=sum;
	}
	return min;
}

int main ()
{
	int i,n,dx,dy;
	ifstream f("tribute.in");
	ofstream g("tribute.out");
	f>>n>>dx>>dy;
	for(i=1;i<=n;i++)
		f>>x[i]>>y[i];
	f.close();
	g<<solve(x,n,dx)+solve(y,n,dy);
	g.close();
	return 0;
}