Pagini recente » Cod sursa (job #1951545) | Cod sursa (job #1539909) | Cod sursa (job #756790) | Cod sursa (job #1885262) | Cod sursa (job #185427)
Cod sursa(job #185427)
#include <algorithm>
using namespace std;
#include <stdio.h>
#define MAX 100001
struct smen{
long x,y;
};
smen a[MAX];
long n;
void citire(){
freopen("heavymetal.in","r",stdin);
long i;
scanf("%ld",&n);
++n;
for(i=1;i<n;++i)
scanf("%ld %ld",&a[i].x,&a[i].y);
fclose(stdin);
}
long functie(smen a,smen b){
return a.y<b.y;
}
long B[MAX],poz[MAX];
int main(){
citire();
freopen("heavymetal.out","w",stdout);
sort(a+1,a+n,functie);
long i,j,prec;
B[1]=a[1].y-a[1].x;
poz[1]=0;
for(i=2;i<n;++i){
if(a[i-1].y<=a[i].x) {poz[i]=i-1;j=i-1;}
else{
j=poz[i-1];
while(a[j].y>a[i].x)j=poz[j];
poz[i]=j;
}
prec= B[j] + a[i].y - a[i].x;
B[i]=B[i-1]>prec?B[i-1]:prec;
}
printf("%ld",B[n-1]);
return 0;
}