Cod sursa(job #1860962)

Utilizator stoianmihailStoian Mihail stoianmihail Data 28 ianuarie 2017 15:04:45
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <stdio.h>
#include <ctype.h>

#define MAX_N 100000
#define MAX_BUFF 65536

struct cell {
  int x, y;

  cell() {

  }

  bool operator < (const cell &other) {
    return this -> y < other.y;
  }
};

int N, ptr;
char buff[MAX_BUFF];
int max[MAX_N + 1], cost[MAX_N + 1];
cell sorted[MAX_N + 1];

char getChar(FILE *f) {
  if (ptr == MAX_BUFF) {
    fread(buff, 1, MAX_BUFF, f);
    ptr = 0;
  }
  return buff[ptr++];
}

int freef(FILE *f) {
  int result = 0;
  char c;

  do {
    c = getChar(f);
  } while (!isdigit(c));
  do {
    result = (result << 3) + (result << 1) + c - '0';
    c = getChar(f);
  } while (isdigit(c));
  return result;
}

int MAX(int X, int Y) {
  return X > Y ? X : Y;
}

void sort(int begin, int end) {
  int b = begin, e = end;
  cell tmp, pivot = sorted[(b + e) >> 1];

  while (b <= e) {
    while (sorted[b] < pivot) {
      b++;
    }
    while (pivot < sorted[e]) {
      e--;
    }
    if (b <= e) {
      tmp = sorted[b];
      sorted[b++] = sorted[e];
      sorted[e--] = tmp;
    }
  }
  if (begin < e) {
    sort(begin, e);
  }
  if (b < end) {
    sort(b, end);
  }
}

int binSearch(int lim, int v) {
  int x = 0, pas = 65536;

  while (pas) {
    if (x + pas <= lim && sorted[x + pas].y <= v) {
      x += pas;
    }
    pas >>= 1;
  }
  return x;
}

int main(void) {
  int i;
  FILE *f = fopen("heavymetal.in", "r");

  N = freef(f);
  for (i = 1; i <= N; i++) {
    sorted[i].x = freef(f);
    sorted[i].y = freef(f);
  }
  fclose(f);

  sort(1, N);

  cost[1] = sorted[1].y - sorted[1].x;
  max[1] = cost[1];
  for (i = 2; i <= N; i++) {
    int pos = binSearch(i - 1, sorted[i].x);
    cost[i] = sorted[i].y - sorted[i].x + max[pos];
    max[i] = MAX(max[i - 1], cost[i]);
  }

  freopen("heavymetal.out", "w", stdout);
  fprintf(stdout, "%d\n", max[N]);
  fclose(stdout);
  return 0;
}