Cod sursa(job #2190774)

Utilizator Iulia25Hosu Iulia Iulia25 Data 31 martie 2018 18:37:52
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>

using namespace std;

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

const int N = 500001;
long long n, dx, dy, maxx, maxy, a, b, M, dif, dif2, I, I2, sb, sb2;
long long minim, minimy;
long long x[N], y[N], cx[N], cy[N];

int main()  {
  fin >> n >> dx >> dy;
  for (int i = 1; i <= n; ++i)  {
    fin >> a >> b;
    ++x[a], ++y[b];
    ++cx[a], ++cy[b];
    if (a > maxx)
      maxx = a;
    if (b > maxy)
      maxy = b;
  }
  M = max(maxx, maxy);
  x[0] = y[0] = 0;
  for (int i = 1; i <= M; ++i)  {
    cx[i] += cx[i - 1];
    cy[i] += cy[i - 1];
    x[i] *= i, y[i] *= i;
    x[i] += x[i - 1];
    y[i] += y[i - 1];
  }
  minim = x[maxx], minimy = y[maxy];
  for (int i = 0; i <= maxx - dx; ++i)  {
    if (i)  {
      sb = cx[i - 1] * i;
      I = x[i - 1];
    } else
      sb = I = 0;
    dif = sb - I;
    sb2 = (cx[maxx] - cx[i + dx]) * (i + dx);
    I2 = x[maxx] - x[i + dx];
    dif2 = I2 - sb2;
    if (dif + dif2 < minim)
      minim = dif + dif2;
  }
  for (int i = 0; i <= maxy - dy; ++i)  {
    if (i)
      dif = cy[i - 1] * i - y[i - 1];
    else
      dif = 0;
    dif2 = y[maxy] - y[i + dy] - (cy[maxy] - cy[i + dy]) * (i + dy);
    if (dif + dif2 < minimy)
      minimy = dif + dif2;
  }
  fout << minim + minimy;
}