Cod sursa(job #952687)

Utilizator primulDarie Sergiu primul Data 23 mai 2013 20:03:53
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<fstream>
#include<algorithm>
 
using namespace std;
 
const int knmax = 50003;
 
long long 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];
  }
 
  long long bestx = 2e14, besty = 2e14;
 
  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;
}