Pagini recente » Cod sursa (job #1743479) | Cod sursa (job #2574374) | Cod sursa (job #1745487) | Cod sursa (job #1583751) | Cod sursa (job #2025571)
#include <fstream>
#include <algorithm>
using namespace std;
const int NMAX = 100000;
int n, i, ans, dp[NMAX + 5], indice, st, dr, mij;
struct Alexutu {
int x, y;
}a[NMAX + 5];
bool cmp(Alexutu a, Alexutu b) {
return b.y > a.y;
}
int main() {
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
cin >> n;
for(i = 1; i <= n; ++i) {
cin >> a[i].x >> a[i].y;
}
sort(a + 1, a + 1 + n, cmp);
for(i = 1; i <= n; ++i) {
st = 1;
dr = i;
while (st < dr) {
mij = (st + dr) / 2;
if(a[mij].y <= a[i].x)
st = mij + 1;
else
dr = mij;
}
mij = (st + dr) / 2;
if(a[mij].y > a[i].x)
--mij;
dp[i] = max(dp[mij] + a[i].y - a[i].x, ans);
ans = max(ans, dp[i]);
}
cout << ans << "\n";
return 0;
}