Cod sursa(job #2322591)

Utilizator _WLZ_zhiyi luo _WLZ_ Data 17 ianuarie 2019 22:00:23
Problema Heavy metal Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  #ifndef DEBUG
  freopen("heavymetal.in", "r", stdin);
  freopen("heavymetal.out", "w", stdout);
  #endif
  int n;
  cin >> n;
  vector< pair<int, int> > v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i].first >> v[i].second;
    v[i].second--;
  }
  sort(v.begin(), v.end());
  vector<int> dp(n), mx(n);
  int last = -1;
  for (int i = 0; i < n; i++) {
    while (last < n && v[max(0, last)].second < v[i].first) {
      last++;
    }
    dp[i] = v[i].second - v[i].first + 1;
    if (last >= 1) {
      dp[i] += mx[last - 1];
    }
    mx[i] = dp[i];
    if (i > 0) {
      mx[i] = max(mx[i], mx[i - 1]);
    }
  }
  cout << *max_element(dp.begin(), dp.end()) << '\n';
  return 0;
}