Pagini recente » Cod sursa (job #2713280) | Cod sursa (job #2621597) | Cod sursa (job #2783585) | Cod sursa (job #366111) | Cod sursa (job #1368662)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int Max = 100005;
int N,DP[Max],Z[Max];
struct SP{
int a,b,timp;
}S[Max];
int Compare(SP pr, SP ul)
{
if(pr.b==ul.b)
return pr.a < ul.a;
return pr.b < ul.b;
}
int Search(int Left, int Right, int pos)
{
while(Left<=Right)
{
int Mid = (Left + Right) / 2;
if(S[Mid].b <= pos)
Left = Mid + 1;
else
Right = Mid - 1;
}
return Right;
}
void Read()
{
in>>N;
for(int i=1;i<=N;i++)
{
in>>S[i].a>>S[i].b;
S[i].timp=S[i].b-S[i].a;
}
sort(S+1, S+N+1, Compare);
for(int i=1;i<=N;i++)
{
DP[i]=max(DP[i-1], DP[Search(0,i,S[i].a)]+ S[i].timp);
}
out<<DP[N];
}
int main()
{
Read();
return 0;
}