Cod sursa(job #438690)

Utilizator skyelHighScore skyel Data 10 aprilie 2010 22:56:21
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 2.82 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 0xffffffff
#define in "gutui.in"
#define out "gutui.out"

typedef struct
        {
        unsigned h;
        unsigned g;      
        unsigned 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 swap(unsigned &a, unsigned &b)
     {
     int aux;
     aux=a;
     a=b;
     b=aux;         
     }
void add(unsigned *heap,unsigned n,unsigned value)
     {
     int aux;
     heap[n]=value;
     aux=n;
     while (heap[aux] < heap[aux/2] && aux > 1)
           {
           swap(heap[aux],heap[aux/2]);
           if (heap[aux]<heap[aux+1])
              swap(heap[aux],heap[aux+1]);
           aux/=2;           
           
           }
     }


void del(unsigned *heap, unsigned n,unsigned pos)
     {
     heap[pos]=heap[n];
     heap[n]=INF;
     while (((n-1)/2) >= pos)
           {
           swap(heap[pos*2],heap[pos]);
           pos*=2;
           }
     }

void print(unsigned * heap,unsigned n)
     {
     unsigned i;
     for (i=1;i<=n+1;++i)
         printf("%d ",heap[i]);
     printf("\n");           
     }

int main()
    {
    unsigned n,i,max_height,up_height,taken,sum=0,nr=0,*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--;           
            }
        }
    heap=(unsigned*)calloc(n,sizeof(unsigned));
    for (i = 0;i < n; ++i)
        heap[i]=INF;
    qsort(gutui,n,sizeof(pom),compare);
    taken=0;
    for ( i = 0; i < n; ++i)
        {
        if (taken < gutui[i].coef)
           {
           taken++;
           add(heap,taken,gutui[i].g);
           }
        else
            {
            if (gutui[i].g > heap[1])
               {
               del(heap,taken,1);
               //printf("x");
               //print(heap,taken);
               add(heap,taken,gutui[i].g);
               }     
            }
        //print(heap,taken);
        }    
    for ( i = 1; i <= taken; ++i)
        {
        if (heap[i]!=INF)
           sum+=heap[i];
        }
    printf("%u\n",sum);

    return 0;      
    }