Pagini recente » Cod sursa (job #683435) | Cod sursa (job #1550832) | Cod sursa (job #988382) | Cod sursa (job #1375841) | Cod sursa (job #2987994)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct vrajeala{
int l,r;
} a[100005];
int d[100005];
int n;
bool SmogoSort(vrajeala a, vrajeala b){
return a.r<b.r;
}
int main()
{
int i,c,x,y;
fin >> n;
for(i=1;i<=n;i++){
fin >> a[i].l >> a[i].r;
}
sort(a+1,a+n+1,SmogoSort);
for(i=1;i<=n;i++){
x=a[i].l;
y=a[i].r;
c=y-x;
int st=1,dr=i-1,mij,p=0;
while(st<=dr){
mij=(st+dr)/2;
if(x>=a[mij].r){
p=mij;
st=mij+1;
}
else dr=mij-1;
}
d[i]=max(d[i-1],d[p]+c);
}
fout << d[n];
return 0;
}