Pagini recente » Cod sursa (job #1636808) | Cod sursa (job #2167589) | Rating Budau Sugis Pulis (freak96) | Cod sursa (job #828184) | Cod sursa (job #1208228)
#include <fstream>
#include <algorithm>
#define NMax 1000005
#define r first
#define l second
using namespace std;
pair <int, int> I[NMax];
int N;
long long 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 ()
{
ifstream f("heavymetal.in");
f>>N;
for (int i=1; i<=N; ++i)
{
f>>I[i].l>>I[i].r;
}
}
void Print ()
{
ofstream g("heavymetal.out");
g<<DP[N];
}
int main ()
{
Read ();
Solve ();
Print ();
return 0;
}