Pagini recente » Cod sursa (job #1367123) | Cod sursa (job #2726629) | Cod sursa (job #1838156) | Cod sursa (job #493555) | Cod sursa (job #1028356)
#include<fstream>
#include<algorithm>
#define Nmax 100005
using namespace std;
ifstream eu("heavymetal.in");
ofstream tu("heavymetal.out");
struct Interval{
int left,right;
}Int[Nmax];
int N,DP[Nmax];
bool Cmp(Interval X,Interval Y)
{
return X.right<Y.right;
}
void Read()
{
eu>>N;
for(int i=1;i<=N;i++)
eu>>Int[i].left>>Int[i].right;
sort(Int+1,Int+N+1,Cmp);
}
int Binary(int left,int right,int val)
{
int p=0,middle;
while(left<=right)
{
middle=(left+right)/2;
if(Int[middle].right<=val)
{
p=middle;
left=middle+1;
}
else
right=middle-1;
}
return p;
}
void Solve()
{
for(int i=1;i<=N;i++)
{
int j=Binary(1,i-1,Int[i].left);
DP[i]=max(DP[i-1],DP[j]+Int[i].right-Int[i].left);
}
}
void Print()
{
tu<<DP[N]<<"\n";
}
int main()
{
Read();
Solve();
Print();
return 0;
}