Pagini recente » Cod sursa (job #1967925) | Cod sursa (job #2035221) | Cod sursa (job #467092) | Cod sursa (job #66071) | Cod sursa (job #2153583)
#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++){
Max=t[i].dr-t[i].st;
if(t[i].dr<=t[i-1].st)
Max=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].st>=t[i].dr){
sol=mid;
st=mid+1;
}
else
dr=mid-1;
}
Max=max(Max,d[sol]+t[i].dr-t[i].st);
d[i]=Max;
}
Max=0;
for(i=1;i<=n;i++)
if(d[i]>Max)
Max=d[i];
cout<<Max;
return 0;
}