Pagini recente » Cod sursa (job #376715) | Cod sursa (job #2705899) | Cod sursa (job #1727888) | Cod sursa (job #2599481) | Cod sursa (job #2638586)
#include <bits/stdc++.h>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int lim=1e5+4;
const int inf=2e9+7;
pair<int,int> v[lim];
int dp[lim];
bool mycmp(pair<int,int> p1,pair<int,int> p2)
{
if(p1.second==p2.second)
return p1.first>p2.first;
return p1.second<p2.second;
}
int main()
{
int n;
in>>n;
for(int i=1;i<=n;++i)
in>>v[i].first>>v[i].second;
sort(v+1,v+n+1,mycmp);
int l,r,med;
for(int i=1;i<=n;++i)
{
dp[i]=dp[i-1];
if(v[i].first<v[1].second)
dp[i]=max(dp[i],v[i].second-v[i].first);
else
{
l=1,r=i-1;
while(l<r)
{
if(r==l+1)
med=r;
else med=(l+r)/2;
if(v[med].second<=v[i].first)
l=med;
else r=med-1;
}
dp[i]=max(dp[i],dp[l]+v[i].second-v[i].first);
}
}
out<<dp[n]<<'\n';
return 0;
}