Cod sursa(job #2112138)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 23 ianuarie 2018 08:38:11
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("heavymetal.in");
ofstream fo("heavymetal.out");

const int lim = 1e5;

struct interval{
  int st, dr;
} v[lim + 1];

int pa[lim + 1], d[lim + 1];

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

inline int CB(int x, int n){
  int ans = 0;
  for(int pas = 1 << 16; pas > 0; pas /= 2)
    if(pas + ans <= n && v[pas + ans].dr <= x)
      ans += pas;
  return ans;
}

int main()
{
  int n;
  fi >> n;
  for(int i = 1; i <= n; i++)
    fi >> v[i].st >> v[i].dr;
  sort(v + 1, v + 1 + n, cmp);
  for(int i = 1; i <= n; i++)
    d[i] = max(d[i - 1], d[CB(v[i].st, n)] + v[i].dr - v[i].st);
  fo << d[n];
  fi.close();
  fo.close();
  return 0;
}