Cod sursa(job #741418)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 25 aprilie 2012 23:12:30
Problema Tribute Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 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,maximx,maximy,dx,dy,Ssum,Dsum;
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];
    }

  poz=1;
  maximx=inf;



  for(i=1; i<=n; ++i)
    {
      dreapta=X[i];
      stanga=X[i]-dx;

      if (stanga<0)
        stanga=0;

      while (stanga>X[poz])
        ++poz;

      if (X[poz]>stanga)
        --poz;

      Ssum=stanga*poz-Xsum[poz];
      Dsum=(Xsum[n]-Xsum[i-1])-dreapta*(n-i+1);

      if (Ssum+Dsum<maximx)
        maximx=Ssum+Dsum;
    }



  poz=1;
  maximy=inf;

  for(i=1; i<=n; ++i)
    {
      dreapta=Y[i];
      stanga=Y[i]-dy;

      if (stanga<0)
        stanga=0;

      while (stanga>X[poz])
        ++poz;

      if (X[poz]>stanga)
        --poz;

      Ssum=stanga*poz-Ysum[poz];
      Dsum=(Ysum[n]-Ysum[i-1])-dreapta*(n-i+1);

      if (Ssum+Dsum<maximy)
        maximy=Ssum+Dsum;

    }


  g<<maximx+maximy<<'\n';

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