Pagini recente » Cod sursa (job #1845616) | Cod sursa (job #1558429) | Cod sursa (job #3173929) | Cod sursa (job #2976396) | Cod sursa (job #1804654)
#include<bits/stdc++.h>
#define maxN 100005
using namespace std;
pair<int,int> v[maxN];
int n,dp[maxN],x,st,dr,mid,sol;
bool cmp(pair <int,int> a,pair<int,int> b)
{
if(a.second<b.second) return 1;
return 0;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i].first,&v[i].second);
}
sort(v+1,v+n+1,cmp);
dp[1]=v[1].second-v[1].first;
for(int i=2;i<=n;i++)
{
dp[i]=dp[i-1];
x=v[i].first;
st=1;
dr=i-1;
sol=0;
while(st<=dr)
{
mid=(st+dr)>>1;
if(v[mid].second<=x)
{
sol=mid;
st=mid+1;
}
else dr=mid-1;
}
dp[i]=max(dp[i],dp[sol]+v[i].second-v[i].first);
}
printf("%d\n",dp[n]);
return 0;
}