Pagini recente » Cod sursa (job #351840) | Cod sursa (job #167779) | Cod sursa (job #3283066) | Cod sursa (job #521214) | Cod sursa (job #759990)
Cod sursa(job #759990)
#include <cstdio>
#include <algorithm>
#define NMax 1000005
#define r first
#define l second
#define LL long long
using namespace std;
pair <int, int> I[NMax];
int N;
LL DP[NMax];
inline int BSearch (int X, int R)
{
int L=0, P=0;
while (L<=R)
{
int Mid=(L+R)/2;
if (I[Mid].r<=X) P=Mid, L=Mid+1;
else R=Mid-1;
}
return P;
}
void Solve ()
{
sort (I+1, I+N+1);
for (int i=1; i<=N; ++i)
{
int j=BSearch (I[i].l, i-1);
DP[i]=max (DP[i-1], DP[j]+I[i].r-I[i].l);
}
}
void Read ()
{
freopen ("heavymetal.in", "r", stdin);
scanf ("%d", &N);
for (int i=1; i<=N; ++i)
{
scanf ("%d %d", &I[i].l, &I[i].r);
}
}
void Print ()
{
freopen ("heavymetal.out", "w", stdout);
printf ("%lld\n", DP[N]);
}
int main ()
{
Read ();
Solve ();
Print ();
return 0;
}