Pagini recente » Cod sursa (job #2278492) | Cod sursa (job #2587022) | Cod sursa (job #1933093) | Cod sursa (job #3292650) | Cod sursa (job #1875623)
#include <cstdio>
#include <algorithm>
#define maxN 100000
using namespace std;
struct interval{
int st, dr;
}v[maxN+1];
int best[maxN+1];
bool cmp(interval A, interval B){
if (A.dr==B.dr)
return A.st<B.st;
return A.dr<B.dr;
}
inline int maxim(int A, int B){ return (A>B ? A:B);}
int binarySearch(int l, int r, int val){
int mid, pos=r;
while (l<=r){
mid=(l+r)/2;
if (v[mid].dr<=val){
pos=mid;
l=mid+1;
}else{
r=mid-1;
}
}
return pos;
}
int main(){
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
int N, i, pos;
scanf("%d", &N);
for (i=1; i<=N; i++)
scanf("%d%d", &v[i].st, &v[i].dr);
sort(v+1, v+N+1, cmp);
for (i=1; i<=N; i++){
pos=binarySearch(1, i, v[i].st);
best[i]=maxim(best[i-1], best[pos]+v[i].dr-v[i].st);
}
printf("%d\n", best[N]);
return 0;
}