Cod sursa(job #145056)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 28 februarie 2008 12:34:30
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#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;
}