Cod sursa(job #437238)

Utilizator adela.balasaAdela Balasa adela.balasa Data 9 aprilie 2010 15:21:16
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 1.36 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int h;  //inaltimea
    int g;  //greutatea
}gutuie;

int N,H,U;
gutuie G[100000];
int v[100000]={0};

int compare (const void * a, const void * b) {
    gutuie g1=*(gutuie*)b;
    gutuie g2=*(gutuie*)a;
    if (g1.g==g2.g)
        return (g1.h - g2.h);
    return (g1.g - g2.g);
}

int main() {
    int i;
    int sum=0;

    FILE* in=fopen("gutui.in","r");
    FILE* out=fopen("gutui.out","w");

    fscanf(in,"%d%d%d",&N,&H,&U);

//    G = (gutuie*)calloc(N,sizeof(gutuie));

    for (i=0;i<N;i++)
        fscanf(in,"%d%d",&G[i].h,&G[i].g);

    qsort (G,N,sizeof(gutuie),compare);

//    int maxl=(H-getHmin())/U+2;
//    v = (int *)calloc(maxl,sizeof(int));

    int nrelem=0;
    for (i=0;i<N;i++) {
        int level=(H-G[i].h)/U+1;
        while (v[level]==1 && level>0)
            level--;
        if (level!=0) {
            v[level]=1;
            sum+=G[i].g;
//            nrelem++;
        }
    }

//    for (i=0;i<maxl;i++)
//        printf("%d ", v[i]);
//    i=0;
//    while(nrelem) {
//        i++;
//        if (v[i]>0) {
//            nrelem--;
//            sum+=v[i];
//        }
//    }

//    for (i=0;i<maxl;i++)
//        sum+=v[i];


    fprintf(out,"%d",sum);


//    free(G);
    fclose(in);
    fclose(out);
    return 0;
}