Cod sursa(job #438642)

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

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

int min(int *heap,int a,int b)
    {
    return heap[a]>heap[b]?b:a;        
    }

void del(int *heap, int n,int pos)
     {
     heap[pos]=heap[n];
     while (n >= pos*2)
           {
           if (heap[pos*2] < heap[pos*2+1])
              {
              swap(heap[pos*2],heap[pos]);
              pos*=2;
              }
           else        
              {
              swap(heap[pos*2+1],heap[pos]);
              pos=pos*2+1;
              }
           }
     }

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

int main()
    {
    int 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=(int*)calloc(n,sizeof(int));
     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)
        sum+=heap[i];
    printf("%d\n",sum);

    return 0;      
    }