Cod sursa(job #1860948)

Utilizator stoianmihailStoian Mihail stoianmihail Data 28 ianuarie 2017 14:59:38
Problema Heavy metal Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <stdio.h>

#define MAX_N 100000

struct cell {
  int x, y;

  cell() {

  }

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

int N;
int max[MAX_N + 1], cost[MAX_N + 1];
cell sorted[MAX_N + 1];

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");

  fscanf(f, "%d", &N);
  for (i = 1; i <= N; i++) {
    fscanf(f, "%d %d", &sorted[i].x, &sorted[i].y);
  }
  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", cost[N]);
  fclose(stdout);
  return 0;
}