Cod sursa(job #1663476)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 26 martie 2016 00:31:48
Problema Lupul Urias si Rau Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <cstdio>
#define MAXN 100000
int D[MAXN],A[MAXN];
//int H[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);
}
/*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(tata(nod)>=0&&H[nod]<H[tata(nod)]){
         swap(nod,tata(nod),H);
         nod=tata(nod);
    }
}
inline void coborare(int nod,int n){
    int aux,flag=1;
    while(nod<n&&flag){
        flag=0;
        aux=nod;
        if(lson(nod)<n&&H[nod]<H[lson(nod)])
           aux=lson(nod);
        if(rson(nod)<n&&Ha[nod]<H[rson(nod)]&&H[lson(nod)]<H[rson(nod)])
           aux=rson(nod);
        if(nod!=aux)
           flag=1;
        swap(nod,aux,H);
        nod=aux;
    }
} */
int main(){
    FILE*fi,*fout;
    int n,x,l,i,e,max;
    long long s,pas;
    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);
    e=n-1;
    pas=s=0;
    while(e>=0){
        max=0;
        while(e>=0&&x-l+1<=D[e]+pas&&D[e]+pas<=x){
           //H[m++]=A[e];
           //urcare(m-1);
           if(A[e]>max)
             max=A[e];
           e--;
        }
        s=s+max;
        pas+=l;
        while(e>=0&&D[e]+pas>x)
           e--;
    }
    fprintf(fout,"%lld" ,s);
    fclose(fi);
    fclose(fout);
    return 0;
}