Pagini recente » Cod sursa (job #384102) | Cod sursa (job #1969350) | Cod sursa (job #344297) | Cod sursa (job #3181586) | Cod sursa (job #522236)
Cod sursa(job #522236)
#include<stdio.h>
#include<algorithm>
using namespace std;
struct formatie
{
int x,y;
};
formatie f[100010];
int t[100010],c[100010];
bool cmp(formatie a,formatie b)
{
return a.y<b.y;
}
long bs(int a,int b)
{
int st,dr,med,last=0;
st=1;
dr=b;
while (st<=dr)
{
med=(st+dr)/2;
if (f[med].y<=a)
{
last=med;
st=med+1;
}
else
dr=med-1;
}
return last;
}
/*int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int last,max,i,n;
scanf("%ld",&n);
for (i=1;i<=n;i++)
scanf("%ld%ld",&f[i].x,&f[i].y);
sort(f+1,f+n+1,cmp);
max=f[n].y;
last=1;
for (i=1;i<=max;i++)
{
t[i]=t[i-1];
while (f[last].y==i)
{
if (t[i]<t[f[last].x]+i-f[last].x)
t[i]=t[f[last].x]+i-f[last].x;
last++;
}
}
printf("%ld",t[max]);
}*/
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int last,max,i,n,poz;
scanf("%ld",&n);
for (i=1;i<=n;i++)
scanf("%ld%ld",&f[i].x,&f[i].y);
sort(f+1,f+n+1,cmp);
c[0]=0;c[1]=f[1].y-f[1].x;
for (i=2;i<=n;i++)
{
c[i]=c[i-1];
poz=bs(f[i].x,i-1);
if (c[i]<c[poz]+f[i].y-f[i].x)
c[i]=c[poz]+f[i].y-f[i].x;
}
printf("%ld",c[n]);
}