Cod sursa(job #258043)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 14 februarie 2009 15:48:32
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 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++){
        int j;
        for(j=i;j&&y[j]>x[i];--j);
        B[i]=max(B[i],y[i]-x[i]+B[j]);
    }
    fprintf(fout,"%d\n",B[N]);
    fclose(fin);
    fclose(fout);
    return 0;

}