Pagini recente » Cod sursa (job #2410792) | Cod sursa (job #1000398) | Cod sursa (job #725584) | Cod sursa (job #2879123) | Cod sursa (job #3184841)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
int n,i,k,d[100003];
struct formatie{
int st,dr;
}v[100003];
bool cmp(formatie a,formatie b){
if(a.dr==b.dr)
return a.st<b.st;
return a.dr<b.dr;
}
int main()
{
cin>>n;
for(i=1;i<=n;i++){
cin>>v[i].st>>v[i].dr;
}
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;i++){
int st=1,dr=i-1,poz=0;
while(st<=dr){
int mid=(st+dr)/2;
if(v[mid].dr>v[i].st)
dr=mid-1;
else{
st=mid+1;
poz=mid;
}
}
d[i]=d[poz]+v[i].dr-v[i].st;
d[i]=max(d[i-1],d[i]);
}
cout<<d[n];
return 0;
}