Cod sursa(job #439845)

Utilizator skyelHighScore skyel Data 11 aprilie 2010 19:53:25
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.54 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 0x7fffffff
#define in "gutui.in"
#define out "gutui.out"
#include <functional>
#include <queue>
#include <vector>
using namespace std;
typedef struct
        {
        int h;
        int g;      
        int coef;
        }pom;
int compare2(const void *a,const void *b)   //compare pentru sortare dupa greutate
    {
    pom *x,*y;
    x=(pom*)a;
    y=(pom*)b;
    return -x->g + y->g;
    }

int compare(const void* a,const void* b)    //compare pentru sortare dupa inaltime
    {
    pom *x,*y;
    x=(pom*)a;
    y=(pom*)b;
    if (x->coef != y->coef)
       return x->coef-y->coef;
    else
        return -x->g+y->g;              
    }

int main()
    {
    int n,i,max_height,up_height,taken,sum=0;
    vector<int> heap;
    pom *gutui;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    scanf("%d %d %d",&n,&max_height,&up_height);
    gutui=(pom*)malloc(n*sizeof(pom));
    for (i = 0; i < n; ++i)
        {
        scanf("%d %d",&gutui[i].h,&gutui[i].g);
        gutui[i].coef=(max_height-gutui[i].h)/up_height+1;   /* un coeficient pentru a "rotunji" inaltimile pana la
                                                                ordinul care are relevanta pentru problema */
        if( gutui[i].h > max_height )                        //elimin gutuile la care nu se poate ajunge din start
            {
            i--;
            n--;           
            }
        }
    make_heap (heap.begin(),heap.end());                     //STL::HEAP
    qsort(gutui,n,sizeof(pom),compare);
    taken=0;
    for ( i = 0; i < n; ++i)
        {
        if (taken < gutui[i].coef)                           //daca pot sa iau gutuia fara modificari la solutia anterioara
           {
           taken++;
           heap.push_back(INF - gutui[i].g); push_heap (heap.begin(),heap.end());
           }
        else
            {                                               //modificam solutia anterioara incat sa fie cea mai buna
            if (gutui[i].g > (INF - heap.front()))           
               {
               pop_heap (heap.begin(),heap.end()); 
               heap.pop_back();
               heap.push_back(INF - gutui[i].g); 
               push_heap (heap.begin(),heap.end());
               }     
            }
        }    
    for ( i = 0; i < heap.size(); ++i)                       //calculul greutatii finale
        {
        sum+=INF - heap[i];
        }
    printf("%u\n",sum);
    return 0;      
    }