Cod sursa(job #1665390)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 26 martie 2016 21:54:08
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <cstdio>
#define MAXN 100000
int D[MAXN],A[MAXN];
inline void swap(int b,int e,int *v){
     int aux=v[b];
     v[b]=v[e];
     v[e]=aux;
}
void myqsort(int begin,int end){
    int b=begin,e=end,pivot=D[(b+e)/2];
    while(b<=e){
        while(D[b]<pivot) b++;
        while(D[e]>pivot) e--;
        if(b<=e){
            swap(b,e,D);
            swap(b,e,A);
            b++;e--;
        }
    }
    if(begin<e) myqsort(begin,e);
    if(b<end) myqsort(b,end);
}
int Hl[MAXN];
inline int lson(int nod){
    return 2*nod+1;
}
inline int rson(int nod){
    return 2*nod+2;
}
inline int tata(int nod){
    return (nod-1)/2;
}
inline void urcare(int nod){
    while(nod>0&&Hl[nod]>Hl[tata(nod)]){
         swap(nod,tata(nod),Hl);
         nod=tata(nod);
    }
}
inline void coborare(int nod,int n){
    int aux,flag=1;
    while(nod<n&&flag){
        aux=nod;
        if(lson(nod)<n&&Hl[nod]<Hl[lson(nod)])
           aux=lson(nod);
        if(rson(nod)<n&&Hl[aux]<Hl[rson(nod)])
           aux=rson(nod);
        if(nod==aux)
           flag=0;
        swap(nod,aux,Hl);
        nod=aux;
    }
}
int main(){
    FILE*fi,*fout;
    int i,n,x,l,nh,j,max,pas;
    long long s;
    fi=fopen("lupu.in" ,"r");
    fout=fopen("lupu.out" ,"w");
    fscanf(fi,"%d%d%d" ,&n,&x,&l);
    for(i=0;i<n;i++)
        fscanf(fi,"%d%d" ,&D[i],&A[i]);
    myqsort(0,n-1);
    max=0;
    for(i=0;i<n;i++){
        if(x<D[i])
           D[i]=-1;
        else
           D[i]=(x-D[i])/l;
        if(D[i]>max)
           max=D[i];
    }
    i=nh=s=0;
    pas=max;
    while(i<n&&pas>=0){
        j=i;
        while(j<n&&D[j]==pas){
            Hl[nh++]=A[j];
            j++;
            urcare(nh-1);
        }
        if(nh>0){
          s=s+Hl[0];
          Hl[0]=Hl[nh-1];
          nh--;
          coborare(0,nh);
        }
        i=j;
        pas--;
    }
    fprintf(fout,"%lld" ,s);
    fclose(fi);
    fclose(fout);
    return 0;
}