Cod sursa(job #437013)

Utilizator adela.balasaAdela Balasa adela.balasa Data 9 aprilie 2010 04:12:23
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.17 kb
#include <stdio.h>
#include <stdlib.h>

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

int N,H,U;
gutuie *G;
int *v;

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));
    v = (int *)calloc(1000,sizeof(int));

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

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

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

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

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


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


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