Pagini recente » Borderou de evaluare (job #1221569) | Cod sursa (job #1477775) | Cod sursa (job #539216) | Cod sursa (job #369026) | Cod sursa (job #2628805)
#include <iostream>
#include <stdio.h>
using namespace std;
int n,i,k;
int x[100003];
struct time{
int s,f;
}v[100003];
int Bin(int a,int st,int dr){
int Max=0;
while(st<=dr){
int m=(st+dr)/2;
if(v[m].f<=a)
Max=m,
st=m+1;
else
dr=m-1;
}
return Max;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&v[i].s,&v[i].f);
sort(v+1,v+n+1);
reverse(v+1,v+n+1);
x[1]=v[1].f-v[1].s;
for(i=2;i<=n;i++){
k=Bin(v[i].s,1,i-1);
x[i]=max(x[i-1],x[k]+v[i].f-v[i].s);
}
printf("%d",x[n]);
return 0;
}