Cod sursa(job #1411659)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 31 martie 2015 21:03:14
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include<stdio.h>
#include<algorithm>
#define MAXN 100005
FILE *f=fopen("lupu.in","r"), *g=fopen("lupu.out","w");

using namespace std;

struct Oite{ int d, l; } v[MAXN]; // dati si lana

int N, Lup, Crestere, HP[MAXN], LHP;
long long R = 0;

bool cmp( Oite A, Oite B ){

    if( A.d > B.d || ( A.d == B.d && A.l > B.l ) )
        return 1;
        return 0;
}

void Citire(){
int i, dist, lana;

    fscanf(f,"%d %d %d\n",&N,&Lup,&Crestere);
    for(i=1;i<=N;i++){

        fscanf(f,"%d %d\n",&dist,&lana);

        if( dist <= Lup )
             v[i].d = ( Lup - dist ) / Crestere + 1;
        else v[i].d = 0;

        v[i].l = lana;

    }

}

void Pune( int nr ){
int poz;

    HP[++LHP] = nr;
    poz = LHP;

    while( poz > 1 && HP[poz/2] < HP[poz] ){

        swap( HP[poz], HP[poz/2] );
        poz /= 2;

    }

}

void Scoate(){
int poz, mx, pmx;

    R += 1LL * HP[1];

    if( LHP > 1 )
        HP[1] = HP[LHP];

    LHP--;

    poz = 1;
    while(1){

        if( poz*2 > LHP )
            break;

         mx = HP[poz*2];
        pmx = poz*2;

        if( poz*2+1 <= LHP && HP[poz*2+1] > mx ){
             mx = HP[poz*2+1];
            pmx = poz*2+1;
        }

        if( HP[poz] < mx ){
            swap( HP[poz], HP[pmx] );
            poz = pmx;
        }
        else
            break;

    }

}

void Rezolva(){
int ind, zi, zimax = v[1].d;

    ind = 1;
    for( zi = zimax; zi >= 1; zi -- ){

        while( v[ind].d == zi )
            Pune( v[ind++].l );

        if( LHP > 0 )
            Scoate();

    }   fprintf(g,"%lld\n",R);

}

int main(){

    Citire();
    sort(v+1,v+N+1,cmp);
    Rezolva();

return 0;
}