Pagini recente » Cod sursa (job #2833283) | Cod sursa (job #1788820) | Cod sursa (job #2852122) | Cod sursa (job #2479662) | Cod sursa (job #2628800)
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int n,i,k;
int x[100003];
struct time{
int s,f;
}v[100003];
int Comp(time a,time b){
return a.f<b.f;
}
int Bin(int a,int st,int dr){
int Max;
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,Comp);
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;
}