Pagini recente » Cod sursa (job #3138838) | Cod sursa (job #977726) | Cod sursa (job #2503637) | Cod sursa (job #2554015) | Cod sursa (job #927132)
Cod sursa(job #927132)
#include<stdio.h>
#include<algorithm>
using namespace std;
struct TYPE { int x, y; };
TYPE c[100010];
int res[100010];
bool cmp(TYPE a, TYPE b)
{
return a.y<b.y;
}
int bs (int val, int dr)
{
int st=1,med,last;
last=0;
while(st<=dr)
{
med=(st+dr)>>1;
if(c[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 poz,t1,t2,n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&t1,&t2);
c[i].x=t1; c[i].y=t2;
}
sort(c+1,c+1+n,cmp);
for(i=1;i<=n;i++)
{
poz=bs(c[i].x,i-1);
res[i]=max(res[i-1],res[poz]+c[i].y-c[i].x);
}
printf("%d\n",res[n]);
return 0;
}