Pagini recente » Cod sursa (job #3268317) | Cod sursa (job #1680276) | Cod sursa (job #34552) | Cod sursa (job #2210642) | Cod sursa (job #1431072)
//horatiu11
# include <cstdio>
# include <algorithm>
# define nmax 100001
using namespace std;
int n,sol[nmax];
struct interval{int a,b;}v[nmax];
inline bool cmp(interval x, interval y)
{
return (x.b<y.b);
}
int main()
{
int i,l,r,m,poz;
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)
{
l=1;r=i-1;poz=0;
while(l<=r)
{
m=(l+r)/2;
if(v[m].b<=v[i].a)l=m+1,poz=m;
else r=m-1;
}
sol[i]=max(sol[i-1],sol[poz]+v[i].b-v[i].a);
}
printf("%d\n",sol[n]);
return 0;
}