Pagini recente » Cod sursa (job #1359118) | Cod sursa (job #2568726) | Cod sursa (job #1250989) | Cod sursa (job #2405345) | Cod sursa (job #742300)
Cod sursa(job #742300)
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,i,p=0;
struct STRUCT {int s,f;};
STRUCT a[100005];
inline bool cmp(STRUCT a,STRUCT b)
{
return a.f<b.f;
}
int V[100005];
inline int caut(int v)
{
int st=1,dr=n,med,last=0;
while (st<=dr)
{
med=st+(dr-st)/2;
if (a[med].f<=v) {st=med+1;last=V[med];}
else dr=med-1;
}
return last;
}
int main ()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&a[i].s,&a[i].f);
sort(a+1,a+n+1,cmp);
V[1]=a[1].f-a[1].s;
for(i=2;i<=n;i++)
V[i]=max(V[i-1],caut(a[i].s)+a[i].f-a[i].s);
printf("%d",V[n]);
return 0;
}