Pagini recente » Cod sursa (job #2509849) | Cod sursa (job #1964585) | Cod sursa (job #609919) | Cod sursa (job #2000791) | Cod sursa (job #1151372)
#include <cstdio>
#include <vector>
#include <algorithm>
#define Nmax 100005
using namespace std;
struct nr
{
int a,b;
};
nr v[Nmax];
int dp[Nmax];
inline bool Cmp(const nr A, const nr B)
{
if(A.b==B.b)
return A.a<B.a;
return A.b<B.b;
}
inline int BSearch(int poz)
{
int st=1,dr=poz,mij;
while(st<=dr)
{
mij=(st+dr)/2;
if(v[mij].b<=v[poz].a)
st=mij+1;
else
dr=mij-1;
}
mij=(st+dr)/2;
if(mij && v[mij].b>v[poz].a)
--mij;
return mij;
}
int main()
{
int i,N,ind=0;
freopen ("heavymetal.in","r",stdin);
freopen ("heavymetal.out","w",stdout);
scanf("%d", &N);
for(i=1;i<=N;++i)
scanf("%d%d", &v[i].a,&v[i].b);
sort(v+1,v+N+1,Cmp);
for(i=1;i<=N;++i)
dp[i]=max(dp[i-1],dp[BSearch(i)]+v[i].b-v[i].a);
printf("%d\n", dp[N]);
return 0;
}