Cod sursa(job #438763)

Utilizator skyelHighScore skyel Data 11 aprilie 2010 00:03:58
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.32 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 std::priority_queue<
     unsigned,
     std::vector<unsigned>,
     std::greater<int>
> min_heap_of_ints;
typedef struct
        {
        int h;
        int g;      
        int coef;
        }pom;
int compare2(const void *a,const void *b)
    {
    pom *x,*y;
    x=(pom*)a;
    y=(pom*)b;
    return -x->g + y->g;
    }

int compare(const void* a,const void* b)
    {
    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;              
    }

void print(vector<int> heap,int n)
     {
     int i;
     for (i=0;i<n;++i)
         printf("%d ",heap[i]);
     printf("\n");           
     }

int main()
    {
    int n,i,max_height,up_height,taken,sum=0,nr=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;
        if (nr < gutui[i].coef)
           nr = gutui[i].coef;
        if( gutui[i].h > max_height )
            {
            i--;
            n--;           
            }
        }
    make_heap (heap.begin(),heap.end());
    qsort(gutui,n,sizeof(pom),compare);
    taken=0;
    for ( i = 0; i < n; ++i)
        {
        if (taken < gutui[i].coef)
           {
           taken++;
           heap.push_back(INF - gutui[i].g); push_heap (heap.begin(),heap.end());
           }
        else
            {
            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());
               }     
            }
        //print(heap,heap.size());
        }    
    for ( i = 0; i < heap.size(); ++i)
        {
        sum+=INF - heap[i];
        }
    printf("%u\n",sum);

    return 0;      
    }