Cod sursa(job #2729763)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 25 martie 2021 11:52:46
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e5 + 5;

struct interval {
  int x, y;
} a[NMAX];

bool fcmp(interval A, interval B) {
  if (A.y != B.y)
    return A.y < B.y;
  return A.x < B.x;
}

int dp[NMAX];

void solve() {
  int N;
  fin >> N;
  for (int i = 1; i <= N; ++i)
    fin >> a[i].x >> a[i].y;
  sort (a + 1, a + N + 1, fcmp);
  for (int i = 1; i <= N; ++i) {
    int st = 1, dr = i - 1, best = 0;
    while (st <= dr) {
      int mid = (st + dr) >> 1;
      if (a[mid].y <= a[i].x) {
        best = mid;
        st = mid + 1;
      } else {
        dr = mid - 1;
      }
    }
    dp[i] = max(dp[i - 1], dp[best] + a[i].y - a[i].x);
  }
  fout << dp[N] << '\n';
}

void close_files() {
  fin.close();
  fout.close();
}

int main() {
  solve();
  close_files();
  return 0;
}