Pagini recente » Cod sursa (job #2473402) | Cod sursa (job #2262934) | Cod sursa (job #1194181) | Cod sursa (job #397970) | Cod sursa (job #2481481)
#include <bits/stdc++.h>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
int n,t,dp[100100],ans,l,r,p;
struct hm
{
int l,r;
}v[100100];
bool cmp(hm a,hm b)
{
return a.r<b.r||(a.r==b.r&&a.l<b.l);
}
int main()
{
in>>n;
for(int i=1;i<=n;i++)
in>>v[i].l>>v[i].r;
sort(v+1,v+n+1,cmp);
for(int i=1;i<=n;i++)
{
dp[i]=dp[i-1];
l=0;
r=n;
///caut cea mai mare dreapta mai mica decat stanga intervalului curent
p=0;
while(l<=r)
{
int m=(l+r)/2;
if(v[m].r>v[i].l) r=m-1;
else
{
p=max(m,p);
l=m+1;
}
}
dp[i]=max(dp[i],dp[p]+v[i].r-v[i].l);
ans=max(ans,dp[i]);
}
out<<ans;
return 0;
}