Pagini recente » Cod sursa (job #2046756) | Cod sursa (job #738916) | Cod sursa (job #907503) | Cod sursa (job #2037070) | Cod sursa (job #1312562)
#include <bits/stdc++.h>
using namespace std;
#define l64 long long
#define final second
#define start first
#define Nmax 100013
int i,j,n,a,b;
vector < pair < int,int > > V;
l64 d[Nmax];
bool comp (pair <int, int> a, pair <int,int> b)
{
return (a.final<b.final || (a.final==b.final && a.start<b.start));
}
l64 search(int left, int right,l64 start)
{
int middle,ans;
while(left<=right)
{
middle=(left+right)/2;
if (V[middle].final<=start) left=middle+1;
else right=middle-1;
}
return right;
}
int main(void)
{
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
cin>>n;
for (i=1;i<=n;++i)
{
cin>>a>>b;
V.push_back(make_pair(a,b));
}
sort(V.begin(),V.end(),comp);
d[0]=V[0].final-V[0].start;
for (i=1;i<n;++i)
d[i]=max(d[i-1],V[i].final-V[i].start+d[search(0,i-1,V[i].start)]);
cout<<1LL*d[n-1]<<"\n";
return 0;
}