Cod sursa(job #945544)

Utilizator AnonymouslegionAnonymous Anonymouslegion Data 2 mai 2013 11:29:42
Problema Tribute Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<fstream>
#include<algorithm>

using namespace std;

const int knmax = 50001;

int x[50005], y[50005], lx[50005], ly[50005], rx[50005], ry[50005];

int main(){
  ifstream in("tribute.in");
  ofstream out("tribute.out");

  int n, dx, dy;
  in >> n >> dx >> dy;
  ++dx;
  ++dy;

  for(int i = 1; i <= n; ++i){
    int aux_x, aux_y;
    in >> aux_x >> aux_y;
    ++aux_x;
    ++aux_y;
    ++x[aux_x];
    ++y[aux_y];
  }

  for(int i = 1; i <= knmax; ++i){
    lx[i] = lx[i - 1] + x[i];
    ly[i] = ly[i - 1] + y[i];
  }

  for(int i = 1; i <= knmax; ++i){
    lx[i] = lx[i - 1] + lx[i];
    ly[i] = ly[i - 1] + ly[i];
  }

  for(int i = knmax; i >= 0; --i){
    rx[i] = rx[i + 1] + x[i];
    ry[i] = ry[i + 1] + y[i];
  }

  for(int i = knmax; i >= 0; --i){
    rx[i] = rx[i + 1] + rx[i];
    ry[i] = ry[i + 1] + ry[i];
  }

  int bestx = 2e9, besty = 2e9;

  for(int i = 1; i <= knmax - dx; ++i)
    bestx = min(bestx, lx[i - 1] + rx[i + dx]);
  for(int i = 1; i <= knmax - dy; ++i)
    besty = min(besty, ly[i - 1] + ry[i + dy]);

  out << bestx + besty;

  return 0;
}