Cod sursa(job #2460144)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 22 septembrie 2019 20:57:51
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

const int NMAX = 50002;

int N, dx, dy;
struct p
{
   int x, y;
} a[NMAX];

bool comp1( const p & A, const p & B )
{
   return A.x < B.x;
}

bool comp2( const p & A, const p & B )
{
   return A.y < B.y;
}

void Read()
{
   fin >> N >> dx >> dy;

   for( int i = 1; i <= N; ++i )
     fin >> a[i].x >> a[i].y;
}

void Do()
{
   int v[NMAX] = { 0 };
   int SUM = 0, val, best, x_best, y_best, rg, lf, sum_lf, sum_rg;

   for( int i = 1; i <= N; ++i )
     v[ a[i].x ]++;

   sum_lf = sum_rg = 0;
   lf = rg = 0;

   for( int i = 1; i <= N; ++i )
     if( a[i].x > dx ) { sum_rg += a[i].x - dx;
                         rg++;
                       }

   best = sum_rg;
   x_best = dx;

   for( int i = dx + 1; i <= 50000; ++i )
   {
      lf += v[i - dx - 1];
      sum_lf += lf;
      sum_rg -= rg;
      rg -= v[i];

      val = sum_lf + sum_rg;

      if( best > val )
      {
        best = val;
        x_best = i;
      }
   }

   SUM += best;

   for( int i = 0; i <= 50000; ++i )
     v[i] = 0;

   for( int i = 1; i <= N; ++i )
     v[ a[i].y ]++;

   sum_lf = sum_rg = rg = lf = 0;

   for( int i = 1; i <= N; ++i )
     if( a[i].y > dy ) { sum_rg += a[i].y - dy;
                         rg++;
                        }

   best = sum_rg;
   y_best = dy;

   for( int i = dy + 1; i <= 50000; ++i )
   {
      lf += v[i - dy - 1];
      sum_lf += lf;
      sum_rg -= rg;
      rg -= v[i];

      val = sum_lf + sum_rg;
      if( best > val )
      {
        best = val;
        y_best = i;
      }

     // fout << i << ' ' << lf << '\n';
   }

   SUM += best;

   fout << SUM << '\n';
}

int main()
{
   Read();
   Do();

   fin.close();
   fout.close();

   return 0;
}