Cod sursa(job #440238)

Utilizator mihaiticamihaitica mihaitica Data 11 aprilie 2010 23:07:45
Problema Gutui Scor 20
Compilator cpp Status done
Runda teme_upb Marime 1.48 kb
#include <stdio.h>
#include <algorithm>
#include <list>
#include <vector>
#include <map>
using namespace std;
#define getLevel(Gutuie, H, U) ((H-Gutuie.h)/U)

struct gutuie{
    long int h,g;
};
map<long int, list<gutuie> > Gutui;
vector<long int> arbore;

long int greutate(long int nrNiv){
    long int i, sum=0;
    for(i = nrNiv-1;i>-1;i--){
        if(!Gutui[i].empty()){
            list<gutuie>::iterator it;
            for(it = (Gutui[i]).begin(); it != (Gutui[i]).end(); it++){
                arbore.push_back((*it).g);
                push_heap(arbore.begin(), arbore.end());
            }
        }
        if(!arbore.empty()){
            pop_heap(arbore.begin(),arbore.end());
            sum +=arbore.back();
            arbore.pop_back();
        }
    }
    return sum;
}

int main(){
    long int N,H,U,nrNiv,i;
    gutuie Gutuie;
    FILE *f=fopen("gutui.in","r"), *g=fopen("gutui.out","w");
    fscanf(f,"%li %li %li\n",&N,&H,&U);
    nrNiv = H/U;
    for(i=0;i<N;i++){
        fscanf(f, "%li %li\n", &(Gutuie.h), &(Gutuie.g));
        if(Gutuie.h <= H && Gutuie.h >= 0)
            Gutui[getLevel(Gutuie,H,U)].push_front(Gutuie);
    }/*
    for(i=0;i<nrNiv;i++){
        fprintf(g, "\n%i.",i);
        list<gutuie>::iterator it;
        for(it = (Gutui[i]).begin(); it != (Gutui[i]).end(); it++)
            fprintf(g,"%i %i|", (*it).h, (*it).g);
    }*/
    fprintf(g,"%li", greutate(nrNiv));
    fclose(f);
    fclose(g);
    return 0;
}