Cod sursa(job #2021579)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 13 septembrie 2017 22:49:58
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>
#include <algorithm>

const int INF = 2e9;
const int MAXN = 1e5;

struct Form {
  int x, y;
} v[MAXN + 1];

int d[MAXN + 1];

inline int cmp(Form a, Form b) {
  return a.y < b.y;
}

inline int max(int a, int b) {
  return a > b ? a : b;
}

inline int bins(int st, int dr, int val) {
  int m, l = INF;
  while (st <= dr) {
    m = (st + dr) >> 1;
    if (v[m].y <= val) {
      st = m + 1;
      l = m;
    } else {
      dr = m - 1;
    }
  }
  return l;
}

int main() {
  int n, poz, ans;
  FILE *f = fopen("heavymetal.in", "r");
  fscanf(f, "%d", &n);
  for (int i = 1; i <= n; ++i) {
    fscanf(f, "%d%d", &v[i].x, &v[i].y);
  }
  fclose(f);
  std::sort(v + 1, v + n + 1, cmp);
  ans = 0;
  for (int i = 1; i <= n; ++i) {
    poz = bins(1, i - 1, v[i].x);
    if (poz == INF) {
      d[i] = max(d[i - 1], v[i].y - v[i].x);
    } else {
      d[i] = max(d[i - 1], v[i].y - v[i].x + d[poz]);
    }
    if (ans < d[i]) {
      ans = d[i];
    }
  }
  f = fopen("heavymetal.out", "w");
  fprintf(f, "%d\n", ans);
  fclose(f);
  return 0;
}