Pagini recente » Cod sursa (job #2748190) | Cod sursa (job #1312687)
#include<fstream>
#include<algorithm>
#define max(a,b) a>b ? a : b
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
const int N = 100003;
struct interval{
int l,r;};
interval a[N];
int n,i;
long long best[N],rs;
bool comp(interval i1,interval i2){
return (i1.r < i2.r); }
int main()
{
cin>>n;
for (i=1;i<=n;i++)
cin>>a[i].l>>a[i].r;
sort(a+1,a+n+1,comp);
rs=best[1]=a[1].r-a[1].l;
for (i=2;i<=n;i++){
best[i]=best[i-1];
int l=1,r=i-1;
if (a[1].r>a[i].l) {
best[i]=a[i].r-a[i].l;
continue;
}
int sol;
while (l<=r){
int m=(l+r)/2;
if (a[m].r<=a[i].l)
sol=m,l=m+1;
else r=m-1;
}
best[i]=max(best[i],best[sol]+a[i].r-a[i].l);
rs=max(rs,best[i]);
}
cout<<rs;
return 0;
}