Pagini recente » Profil NicuPresedinte | Cod sursa (job #1337059) | Cod sursa (job #2984550) | Cod sursa (job #2694557) | Cod sursa (job #2351218)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef signed long long ll;
typedef unsigned int uint;
const int nmax = 100005;
struct interval {
uint start;
uint finish;
};
struct comp {
bool operator()(const interval &left, const interval &right) {
if (left.finish == right.finish)
return left.start < right.start;
return left.finish < right.finish;
}
};
interval v[nmax];
uint dp[nmax];
uint n;
uint find_best(uint value, uint right) {
uint left = 1;
uint mid;
while (left <= right) {
mid = (left + right) / 2;
if (v[mid].finish <= value) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
int main() {
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
scanf("%u", &n);
for (uint i = 1; i <= n; i++) {
scanf("%u %u", &v[i].start, &v[i].finish);
}
sort(v + 1, v + n + 1, comp());
dp[1] = v[1].finish - v[1].start;
for (uint i = 2; i <= n; i++) {
uint j = find_best(v[i].start, i - 1); // find best j such that v[j].finish <= v[i].start
dp[i] = max(dp[i - 1], dp[j] + v[i].finish - v[i].start);
}
printf("%u\n", dp[n]);
/*for (uint i = 0;i<n;i++){
cout<<v[i].start <<" "<<v[i].finish<<endl;
}*/
return 0;
}