Cod sursa(job #1851920)

Utilizator TincaMateiTinca Matei TincaMatei Data 20 ianuarie 2017 12:04:06
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <cstdio>
#include <algorithm>

const int MAX_N = 100000;
struct Interval {
  int a, b;
} v[MAX_N];

int d[1+MAX_N];

bool cmp(Interval a, Interval b) {
  return a.b < b.b;
}

int bins(int st, int dr, int x) {
  int mid;
  while(dr - st > 1) {
    mid = (st + dr) / 2;
    if(v[mid].b <= x)
      st = mid;
    else
      dr = mid;
  }
  return st;
}

int main() {
  int n, poz, lft;
  FILE *fin = fopen("heavymetal.in", "r");
  fscanf(fin, "%d", &n);
  for(int i = 1; i <= n; ++i)
    fscanf(fin, "%d%d", &v[i].a, &v[i].b);
  fclose(fin);

  std::sort(v + 1, v + 1 + n, cmp);
  for(int i = 1; i <= n; ++i) {
    d[i] = d[i - 1];
    lft = bins(0, i, v[i].a);
    if(d[lft] + v[i].b - v[i].a > d[i])
      d[i] = d[lft] + v[i].b - v[i].a;
  }

  FILE *fout = fopen("heavymetal.out", "w");
  fprintf(fout, "%d", d[n]);
  fclose(fout);
  return 0;
}