Pagini recente » Cod sursa (job #896621) | Cod sursa (job #2875867) | Cod sursa (job #2430825) | Cod sursa (job #2228516) | Cod sursa (job #145056)
Cod sursa(job #145056)
#include <stdio.h>
#include <stdlib.h>
#define max(a,b) ((a>b)?a:b)
long n,i,a[100005],b[100005],ind[100005];
long x[100005],m[100005],q;
long low,high,mid;
int comp(const void * n1, const void *n2){
return (b[*((long*)n1)]-b[*((long*)n2)]);
}
int main(){
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%ld",&n);
for (i=1;i<=n;i++){
scanf("%ld %ld",&a[i],&b[i]);
ind[i]=i;
}
qsort(ind+1,n,sizeof(long),comp);
for (i=1;i<=n;i++){
if (x[q]!=b[i])q++;
x[q]=b[ind[i]];
m[q]=m[q-1];
low=1;
high=q;
while (low<high){
mid=(low+high)/2;
if (x[mid]>a[ind[i]])
high=mid;
else
low=mid+1;
}
if (low<q&&x[low]==a[ind[i]])
m[q]=max(m[q],m[low]+b[ind[i]]-a[ind[i]]);
else m[q]=max(m[q],m[low-1]+b[ind[i]]-a[ind[i]]);
}
printf("%ld\n",m[q]);
return 0;
}