Cod sursa(job #1254491)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 2 noiembrie 2014 20:11:38
Problema Heavy metal Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <stdio.h>
#define MAXN 100000
int a[MAXN+1], b[MAXN+1], s[MAXN+1], n;
inline int tata(int p){
    return p/2;
}
inline int fiust(int p){
    return p*2;
}
inline int fiudr(int p){
    return p*2+1;
}
inline void schimba(int p1, int p2){
    int aux;
    aux=a[p1];
    a[p1]=a[p2];
    a[p2]=aux;
    aux=b[p1];
    b[p1]=b[p2];
    b[p2]=aux;
}
inline void coborare(int p){
    int f, q;
    f=1;
    while((f==1)&&(fiust(p)<=n)){
        q=fiust(p);
        if((fiudr(p)<=n)&&(b[fiudr(p)]>b[q])){
            q=fiudr(p);
        }
        if(b[q]>b[p]){
            schimba(p, q);
            p=q;
        }else{
            f=0;
        }
    }
}
inline void heapify(){
    int i;
    for(i=tata(n); i>0; i--){
        coborare(i);
    }
}
inline void heapSort(){
    while(n>1){
        schimba(1, n);
        n--;
        coborare(1);
    }
}
int main(){
    int cn, i, rez, pas;
    FILE *fin, *fout;
    fin=fopen("heavymetal.in", "r");
    fout=fopen("heavymetal.out", "w");
    fscanf(fin, "%d", &n);
    for(i=1; i<=n; i++){
        fscanf(fin, "%d%d", &a[i], &b[i]);
    }
    cn=n;
    heapify();
    heapSort();
    n=cn;
    for(i=1; i<=n; i++){
        s[i]=s[i-1];
        rez=0;
        for(pas=1<<16; pas!=0; pas>>=1){
            if((rez+pas<i)&&(b[rez+pas]<=a[i])){
                rez+=pas;
            }
        }
        if(s[i]<s[rez]+b[i]-a[i]){
            s[i]=s[rez]+b[i]-a[i];
        }
    }
    fprintf(fout, "%d\n", s[n]);
    fclose(fin);
    fclose(fout);
    return 0;
}