Pagini recente » Cod sursa (job #2658481) | Cod sursa (job #1732654) | Cod sursa (job #248122) | Cod sursa (job #1518008) | Cod sursa (job #2822667)
// problema pentru roackeri nespalati
#include <iostream>
#include <fstream>
#include <algorithm>
#define int long long
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct spectacol {
int start, end;
};
const int N = 1e5 + 1;
int dp[N];
spectacol v[N];
bool compare(spectacol a, spectacol b) {
if (a.end != b.end) return a.end < b.end;
return a.start < b.start;
}
signed main() {
int n;
fin >> n;
for (int i = 1; i <= n; i++) fin >> v[i].start >> v[i].end;
sort(v + 1, v + n + 1, compare);
for (int i = 1; i <= n; i++) {
int st = 1, dr = i;
while (dr - st > 1) {
int mij = (st + dr) / 2;
if (v[mij].end > v[i].start) dr = mij;
else st = mij;
}
int j = st;
dp[i] = max(dp[i - 1], dp[j] + v[i].end - v[i].start);
}
fout << dp[n];
return 0;
}