Pagini recente » Cod sursa (job #3252360) | Cod sursa (job #1422169) | Cod sursa (job #3256433) | Cod sursa (job #27923) | Cod sursa (job #929716)
Cod sursa(job #929716)
#include<cstdio>
#include<algorithm>
using namespace std;
struct interval
{
int st,dr;
};
interval a,b,v[100010];
int bs;
int n,i,j,rez,best[100010],temp,tmax;
bool cmp(const interval &a,const interval &b)
{
return a.dr<b.dr;
}
int bins(int st,int dr)
{
int last,med;
while(st<=dr)
{
med=((dr-st)>>1)+st;
if(v[med].dr<=v[i].st)
{
st=med+1;
last=med;
}
else
{
dr=med-1;
}
}
return last;
}
int main()
{
int st,dr;
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&st,&dr);
a.st=st;
a.dr=dr;
v[i]=a;
}
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;i++)
{
best[i]=best[i-1];
temp=bins(1,i);
if(best[temp]+(v[i].dr-v[i].st)>best[i])
best[i]=best[temp]+(v[i].dr-v[i].st);
}
printf("%d\n",best[n]);
return 0;
}