Cod sursa(job #438706)

Utilizator ana.ionana ion ana.ion Data 10 aprilie 2010 23:10:39
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.77 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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;              
    }

int main()
    {
    int j,n,i,max_height,up_height,sum=0,nr=0,*frei;
    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--;           
            }
        }
    qsort(gutui,n,sizeof(pom),compare2);
    frei = (int*)malloc(nr*sizeof(int));
    memset(frei,0,(nr+1)*sizeof(int));
    for (i = 0; i < nr; ++i)
        {
        
        for ( j = gutui[i].coef ; j > 0; j--)
            {
            //printf("%d %d\n",j,frei[j]);
            if (frei[j] == 0)
               {
              // printf("me:%d %d %d \n",gutui[i].h,gutui[i].g,gutui[i].coef);   
               sum += gutui[i].g;
               frei[j] = 1;
               break;        
               }
            }    
        if (j == 0 && nr < n)
           nr++;
        }
    printf("%d\n",sum);

    return 0;      
    }