Cod sursa(job #437167)

Utilizator adela.balasaAdela Balasa adela.balasa Data 9 aprilie 2010 14:05:53
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 1.35 kb
#include <stdio.h>
#include <stdlib.h>

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

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

int getHmin () {
    int min=G[0].h,i;
    for (i=1;i<N;i++)
        if (G[i].h<min)
            min=G[i].h;
    return min;
}

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);

    for (i=0;i<N;i++)
        printf("%d %d\n",G[i].h, G[i].g);

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

//    v[]={0};

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

//    for (i=0;i<maxl;i++)
//        printf("%d ", v[i]);

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


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


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