Pagini recente » Cod sursa (job #2805226) | Cod sursa (job #956105) | Cod sursa (job #3172780) | Cod sursa (job #911103) | Cod sursa (job #1692209)
#include <cstdio>
#include <algorithm>
using namespace std;
struct INTERV
{
int x,y;
};
INTERV v[100005];
int d[100005];
bool cmp(INTERV a,INTERV b)
{
return a.y<b.y;
}
int bs(int st,int dr,int val)
{
int med;
while(st<=dr)
{
med=(st+dr)/2;
if(v[med].y<=val) st=med+1;
else dr=med-1;
}
return st-1;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,x,y,i,j,ans=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
v[i].x=x;
v[i].y=y;
d[i]=-1;
}
d[0]=0;
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;i++)
{
j=bs(1,i-1,v[i].x);
d[i]=max(d[i-1],d[j]+v[i].y-v[i].x);
ans=max(ans,d[i]);
}
printf("%d\n",ans);
return 0;
}