Cod sursa(job #2218427)

Utilizator PetyAlexandru Peticaru Pety Data 4 iulie 2018 14:19:33
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");

struct punk {
  int st, dr;
}v[100002];
int dp[100002], n;

bool cmp (punk x, punk y) {
  return x.dr < y.dr;
}

int main()
{
  fin >> n;
  for (int i = 1; i <= n; i++){
    fin >> v[i].st >> v[i].dr;
  }
  sort (v + 1, v + n + 1, cmp);
  dp[1] = v[1].dr - v[1].st;
  for (int i = 2; i <= n; i++) {
    int st = 1, poz = 0, dr = i - 1;
    while (st <= dr) {
      int mij = (st + dr) / 2;
      if (v[i].st >= v[mij].dr) {
        st = mij + 1;
        poz = mij;
      }
      else
        dr = mij - 1;
    }
    dp[i] = max(dp[i - 1], dp[poz] + v[i].dr - v[i].st);
  }
  fout << dp[n];
  return 0;
}