Pagini recente » Cod sursa (job #2238221) | Cod sursa (job #2224136) | Cod sursa (job #863419) | Cod sursa (job #1156653) | Cod sursa (job #1897536)
#include <cstdio>
#include <algorithm>
using namespace std;
const int Nmax = 1e5+5;
struct band
{
int x, y;
bool operator < (const band &a) const
{
return y < a.y;
}
} a[Nmax];
int dp[Nmax], i, n;
int bs(int val, int i)
{
int st = 1, dr = i-1, mid;
while(st<=dr)
{
mid = (st+dr)/2;
if(a[mid].y<=val) st = mid+1;
else dr = mid-1;
}
return dr;
}
int main()
{
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
scanf("%d", &n);
for(i=1; i<=n; ++i) scanf("%d%d", &a[i].x, &a[i].y);
sort(a+1, a+n+1);
for(i=1; i<=n; ++i)
dp[i] = max(dp[i-1], dp[bs(a[i].x, i)] + a[i].y - a[i].x);
printf("%d\n", dp[n]);
return 0;
}