Pagini recente » Cod sursa (job #2684193) | Cod sursa (job #1213942) | Cod sursa (job #1210970) | Cod sursa (job #996734) | Cod sursa (job #742273)
Cod sursa(job #742273)
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,i,p=0;
struct metal {int s,f;};
metal a[100005];
inline int cmp(metal a,metal b)
{
return a.f<b.f;
}
int V[100005];
inline int caut(int v)
{
int p=1,u=n,m,s=0;
while (p<=u)
{
m=p+(u-p)/2;
if (a[m].f<=v) p=m+1,s=V[m];
else u=m-1;
}
return s;
}
int main ()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
int x;
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++)
{
x=max(V[i-1],caut(a[i].s)+a[i].f-a[i].s);
V[i]=x;
}
printf("%d",V[n]);
return 0;
}