Cod sursa(job #741427)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 25 aprilie 2012 23:50:32
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#define LE 50005
#include <algorithm>
#define inf 1<<30
using namespace std;
ifstream f("tribute.in");
ofstream g("tribute.out");
int X[LE],Y[LE],stanga,dreapta,Xsum[LE],Ysum[LE],poz,n,i,j,dx,dy,Xi,Xmin,Ymin;
int suma,start,top;
int main()
{
  f>>n>>dx>>dy;

  for(i=1; i<=n; ++i)
    f>>X[i]>>Y[i];

  sort(X+1,X+n+1);
  sort(Y+1,Y+n+1);

  for(i=1; i<=n; ++i)
    {
      Xsum[i]=Xsum[i-1]+X[i];
      Ysum[i]=Ysum[i-1]+Y[i];
    }


Xmin=inf;
Ymin=inf;

  for(i=1; i<LE&&i<=X[n]; ++i)
    {
      Xi=i-dx;
      if (Xi<0)
        Xi=0;

      while (X[start+1]<Xi&&top<n)
        ++start;

      while(X[top+1]<=i&&top<n)
        ++top;

      suma=Xi*start-Xsum[start];
      suma+=Xsum[n]-Xsum[top]-i*(n-top);

      if (suma<Xmin)
        Xmin=suma;
    }

/////////
start=0;
top=0;

  for(i=1; i<LE&&i<=Y[n]; ++i)
    {
      Xi=i-dy;
      if (Xi<0)
        Xi=0;

      while (Y[start+1]<Xi&&start<n)
        ++start;

      while(Y[top+1]<=i&&top<n)
        ++top;

      suma=Xi*start-Ysum[start];
      suma+=Ysum[n]-Ysum[top]-i*(n-top);

      if (suma<Ymin)
        Ymin=suma;
    }

g<<Xmin+Ymin<<'\n';

  f.close();
  g.close();
  return 0;
}