Cod sursa(job #258094)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 14 februarie 2009 18:05:12
Problema Heavy metal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<stdio.h>
#define max(a,b) (a>b?a:b)

FILE *fin=fopen("heavymetal.in","r"),
    *fout=fopen("heavymetal.out","w");

int N,x[100005],y[100005],B[100005];
void swap(int i,int j){
    y[i]^=y[j];y[j]^=y[i];y[i]^=y[j];
    x[i]^=x[j];x[j]^=x[i];x[i]^=x[j];
}

int main(){
    fscanf(fin,"%d",&N);
    for(int i=1;i<=N;i++){
        fscanf(fin,"%d %d",&x[i],&y[i]);

        int j=i;
        while(j/2 && y[j/2]<y[j]){
            swap(j,j/2);
            j>>=1;
        }
    }

    int Nh=N;
    while(Nh>1){
        swap(1,Nh);
        --Nh;

        int i=1,j;
        while(1){
            j=i*2;
            if(j>Nh) break;
            if(j+1<=Nh && y[j+1]>y[j]) ++j;
            if(y[j]<y[i]) break;
            swap(j,i);
            i=j;
        }
    }

    for(int i=1;i<=N;i++){

        B[i]=B[i-1];
        int li=1,lf=i-1;
        while(lf-li>1){
            int mij=(li+lf)/2;
            if(x[i]<=y[mij])
                lf=mij;
            else
                li=mij;
        }
        if(x[i]>=y[lf])
            B[i]=max(B[i],y[i]-x[i]+B[lf]);
        else
            B[i]=max(B[i],y[i]-x[i]);

        if(x[i]>=y[li])
            B[i]=max(B[i],y[i]-x[i]+B[li]);
        else
            B[i]=max(B[i],y[i]-x[i]);


    }


    fprintf(fout,"%d\n",B[N]);
    fclose(fin);
    fclose(fout);
    return 0;

}