Cod sursa(job #1412006)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 1 aprilie 2015 02:55:50
Problema Lupul Urias si Rau Scor 68
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct oaie{
    int d;
    int a;
}v[100100];
int n,x,l,dh,i,j,s,nr,h[100100];
FILE *f,*g;
int cmp(oaie a,oaie b){
    return a.d<b.d;
}
void chg(int &a,int &b){
    int aux=a;
    a=b;
    b=aux;
}
void heapins(int n){
    int c=dh;
    int p=dh/2;
    while(p>=1){
        if(v[ h[c] ].a > v[ h[p] ].a){
            chg(h[c],h[p]);
            c=p;
            p/=2;
        }
        else
            break;
    }
}
void heapdel(){
    int p=1;
    int c=2;
    while(c<=dh){
        if( v[ h[c] ].a < v[ h[c+1] ].a && c+1<=dh )
            c++;
        if( v[ h[c] ].a > v[ h[p] ].a ){
            chg(h[c],h[p]);
            p=c;
            c*=2;
        }
        else
            break;
    }
}
int main(){
    f=fopen("lupu.in","r");
    g=fopen("lupu.out","w");
    fscanf(f,"%d%d%d",&n,&x,&l);
    for(i=1;i<=n;i++){
        fscanf(f,"%d%d",&v[i].d,&v[i].a);
    }
    sort(v+1,v+n+1,cmp);
    nr=1;
    for(i=0;i<=x;i+=l){
        while(v[nr].d<=i&&nr<=n){
            dh++;
            h[dh]=nr;
            heapins(nr);
            nr++;
        }
        s+=v[ h[1] ].a;
        chg(h[1],h[dh]);
        dh--;
        heapdel();
    }
    fprintf(g,"%d",s);

    fclose(f);
    fclose(g);
    return 0;
}