Pagini recente » Cod sursa (job #422750) | Cod sursa (job #79705) | Cod sursa (job #2534918) | Cod sursa (job #2906757) | Cod sursa (job #2153612)
#include <fstream>
#include <algorithm>
using namespace std;
int n,i,Max,d[100001],st,dr,mid,sol;
struct numar{
int st;
int dr;
}t[100001];
int cmp(numar a,numar b){
if(a.dr==b.dr)
return(a.st<b.st);
return(a.dr<b.dr);
}
int main()
{
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
cin>>n;
for(i=1;i<=n;i++)
cin>>t[i].st>>t[i].dr;
sort(t+1,t+n+1,cmp);
d[1]=t[1].dr-t[1].st;
for(i=2;i<=n;i++){
d[i]=max(t[i].dr-t[i].st,d[i-1]);
if(t[i].st>=t[i-1].dr)
d[i]=d[i-1]+t[i].dr-t[i].st;
st=1;dr=i-1;
sol=0;
while(st<=dr){
mid=(st+dr)/2;
if(t[mid].dr<=t[i].st){
sol=mid;
st=mid+1;
}
else
dr=mid-1;
}
if(sol!=0)
d[i]=max(d[i],d[sol]+t[i].dr-t[i].st);
}
Max=0;
for(i=1;i<=n;i++)
if(d[i]>Max)
Max=d[i];
cout<<Max;
return 0;
}