Cod sursa(job #1203983)

Utilizator hrazvanHarsan Razvan hrazvan Data 1 iulie 2014 17:48:26
Problema Tribute Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#define MAXN 50000
#define MAXCOORD 50000
#define INF 9000000000000000000
int vx[MAXCOORD + 1], vy[MAXCOORD + 1];
long long st[MAXCOORD + 1], dr[MAXCOORD + 1];

long long min2(long long a, long long b){
  if(a < b) return a;
  return b;
}

long long rezolv(int *v, int dist){
  long long nrst = 0, nrdr = 0, rez = INF;
  int i;
  for(i = 0; i < MAXCOORD + 1; i++){
    if(i != 0)  st[i] = st[i - 1] + nrst;
    nrst += v[i];
  }
  for(i = MAXCOORD; i >= 0; i--){
    if(i != MAXCOORD)  dr[i] = dr[i + 1] + nrdr;
    nrdr += v[i];
  }
  for(i = 0; i < MAXCOORD; i++){
    if(i + dist - 1 <= MAXCOORD){
      rez = min2(rez, st[i] + dr[i + dist - 1]);
    }
  }
  return rez;
}

int main(){
  FILE *in = fopen("tribute.in", "r");
  int n, dx, dy;
  fscanf(in, "%d%d%d", &n, &dx, &dy);
  dx++;  dy++;
  int i, a, b;
  for(i = 0; i < n; i++){
    fscanf(in, "%d%d", &a, &b);
    vx[a]++;  vy[b]++;
  }
  fclose(in);
  long long rezx, rezy;
  rezx = rezolv(vx, dx);
  rezy = rezolv(vy, dy);
  FILE *out = fopen("tribute.out", "w");
  fprintf(out, "%lld", rezx + rezy);
  fclose(out);
  return 0;
}