Cod sursa(job #2190757)

Utilizator Iulia25Hosu Iulia Iulia25 Data 31 martie 2018 18:12:19
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>

using namespace std;

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

const int N = 501;
int n, dx, dy, maxx, maxy, a, b, M, dif, dif2, I, I2, sb, sb2;
int minim = 0x3f3f3f3f, minimy = 0x3f3f3f3f;
int 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];
  }
  for (int i = 0; i <= maxx; ++i)  {
    sb = cx[i] * i;
    if (i)
      I = x[i - 1];
    else
      I = 0;
    dif = sb - I;
    sb2 = (cx[maxx] - cx[i + dx]) * i;
    I2 = x[maxx] - x[i + dx];
    dif2 = I2 - sb2;
    if (dif + dif2 < minim)
      minim = dif + dif2;
  }
  for (int i = 0; i <= maxy; ++i)  {
    if (i)
      dif = cy[i] * i - y[i - 1];
    else
      dif = 0;
    dif2 = y[maxy] - y[i + dy] - (cy[maxy] - cy[i + dy]) * i;
    if (dif + dif2 < minimy)
      minimy = dif + dif2;
  }
  fout << minim + minimy;
}