Pagini recente » Cod sursa (job #12808) | Cod sursa (job #2562634) | Cod sursa (job #1482823) | Cod sursa (job #1082614) | Cod sursa (job #2810866)
#include <fstream>
#include <algorithm>
using namespace std;
int n,rez[100005];
struct Nr
{
int st,dr;
}v[100005];
bool cmp(Nr x,Nr y)
{
if(x.dr!=y.dr)
return x.dr<y.dr;
return x.st<y.st;
}
int c_binara(int x)
{
int st=1,dr=n;
while(st<=dr)
{
int mij=(st+dr)/2;
if(v[mij].dr<=x)
st=mij+1;
else
dr=mij-1;
}
return dr;
}
int main()
{
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i].st>>v[i].dr;
}
sort(v+1,v+n+1,cmp);
int k,j,rezultat=0;
for(int i=1;i<=n;i++)
{
j=c_binara(v[i].st);
rez[i]=max(rez[i-1],rez[j]+v[i].dr-v[i].st);
rezultat=max(rezultat,rez[i]);
}
cout<<rezultat;
return 0;
}