Pagini recente » Cod sursa (job #1637199) | Cod sursa (job #138808) | Cod sursa (job #2617730) | Cod sursa (job #1754218) | Cod sursa (job #2527447)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
pair<long long,long long>v[100005];
long long n,d[100005];
long long caut(long long x,long long i){
long long st=1,dr=i,sol=0;
while(st<=dr){
long long mj=(st+dr)/2;
if(v[mj].first>x)
dr=mj-1;
else{
st=mj+1;
sol=mj;
}
}
return sol;
}
int main()
{
cin>>n;
for(long long i=1;i<=n;i++){
cin>>v[i].second>>v[i].first;
}
sort(v+1,v+n+1);
for(long long i=1;i<=n;i++){
if(v[i].first-v[i].second+caut(v[i].second,i-1)>d[i-1]){
d[i]=v[i].first-v[i].second+caut(v[i].second,i-1);
}
else
d[i]=d[i-1];
}
cout<<d[n];
return 0;
}