Pagini recente » Cod sursa (job #2092943) | Cod sursa (job #858913) | Cod sursa (job #1226401) | Cod sursa (job #1460380) | Cod sursa (job #219910)
Cod sursa(job #219910)
#include <stdio.h>
#include <algorithm>
#define mx 110000
using namespace std;
pair <int, int> a[mx];
int vm[mx];
int n;
int cauta(int p, int u, int lim)
{
if (p > u)
return 0;
int m = (p + u) / 2;
if (a[m].first <= lim && a[m + 1].first > lim)
return m;
else if (a[m].first <= lim)
return (cauta(m + 1, u, lim));
else return (cauta(p, m - 1, lim));
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%ld", &n);
for (int i = 1; i <= n; i++)
scanf("%ld %ld", &a[i].second, &a[i].first);
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++)
vm[i] = max(vm[cauta(0, i - 1, a[i].second)] + a[i].first - a[i].second, vm[i - 1]);
printf("%ld\n", vm[n]);
fclose(stdin);
fclose(stdout);
return 0;
}