Pagini recente » Cod sursa (job #1995181) | Cod sursa (job #1522346) | Cod sursa (job #2535744) | Cod sursa (job #364035) | Cod sursa (job #1849244)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
const int MAX = 100001;
struct interval {
int st, dr;
} v[MAX];
int n, dp[MAX];
bool cmp(interval a, interval b) {
return a.dr < b.dr;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> v[i].st >> v[i].dr;
}
sort(v + 1, v + n + 1, cmp);
for(int i = 1; i <= n; ++i) {
dp[i] = dp[i - 1];
int st = 1, dr = i - 1;
while(st <= dr) {
int mij = (st + dr) / 2;
if(v[mij].dr <= v[i].st) {
st = mij + 1;
} else {
dr = mij - 1;
}
}
if(dp[dr] + v[i].dr - v[i].st > dp[i]) {
dp[i] = dp[dr] + v[i].dr - v[i].st;
}
}
cout << dp[n];
return 0;
}