Pagini recente » Cod sursa (job #1608728) | Cod sursa (job #1427270) | Cod sursa (job #1399617) | Cod sursa (job #827287) | Cod sursa (job #1206842)
#include<cstdio>
#include<algorithm>
using namespace std;
struct metal
{
int x,y;
};
metal v[100005];
int d[100005];
int cmp(metal a,metal b)
{
return a.y<b.y;
}
int bs(int st,int dr,int val)
{
int med,last=-1;
while(st<=dr)
{
/*med=(st+dr)/2
med=st+(dr-st)/2;*/
med=(st+dr)>>1;
if (v[med].y<=val)
last=med,st=med+1;
else
dr=med-1;
}
return last;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,i,last;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp);
d[1]=v[1].y-v[1].x;
for(i=2;i<=n;i++)
{
d[i]=d[i-1];
last=bs(1,i-1,v[i].x);
if (last==-1)
{
if (d[i]<v[i].y-v[i].x)
d[i]=v[i].y-v[i].x;
}
else
if (d[i]<d[last]+v[i].y-v[i].x)
d[i]=d[last]+v[i].y-v[i].x;
}
printf("%d\n",d[n]);
return 0;
}