Cod sursa(job #427355)

Utilizator lucicanuAndrei-Lucian Croitoru lucicanu Data 27 martie 2010 19:45:33
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.81 kb
# include <stdio.h>
# include <stdlib.h>

# define MAXL 100000

typedef struct gut{
               int h;
               int v;
               int p;
               }Gutuie;

int compare(const void* a, const void* b){
    Gutuie *aa = (Gutuie*)a;
    Gutuie *bb = (Gutuie*)b;
    if (aa->p < bb->p)
       return -1;
    else
        if (aa->p > bb->p)
           return 1;
        else
            if (aa->v < bb->v)
               return 1;
            else
                return -1;
}

int compare2(const void* a, const void* b){
    int *aa = (int*)a;
    int *bb = (int*)b;
    if ( *aa < *bb)
       return 1;
    return -1;
}

int main(){
    int n, H, U, i, j, sol[MAXL], nsol, pas, s;
    Gutuie g[MAXL];
    FILE *fin, *fout;
    fin=fopen("gutui.in","r");
    fout=fopen("gutui.out","w");
    
    fscanf(fin,"%d%d%d",&n, &H, &U);
    for (i=0;i<n;i++){
        fscanf(fin,"%d%d",&g[i].h,&g[i].v);
        g[i].p = (H - g[i].h)/U + 1;
    }
    
    qsort(g,n,sizeof(Gutuie),*compare);
    /*for (i=0;i<n;i++){
        printf("%d ",g[i].v);
    }*/
    nsol = 0;
    for (i=0;i<n;i++){
        if (i==0 || g[i].p != g[i-1].p){ //pasul urmator;
           pas = g[i].p;
           for (j=i;j<n && g[j].p == pas && j-i<pas;j++){//parcurg gutuile de la pasul curent(sunt in ordine descrescatoare;
               if (nsol<pas){
                  sol[nsol++] = g[j].v;
               }
               else{
                    if (g[j].v > sol[nsol-1]){
                       sol[nsol-1] = g[j].v;
                       qsort(sol,nsol,sizeof(int),*compare2);
                    }
               }
           }
        }
    }
    s = 0;
    for (i=0;i<nsol;i++)
        s+=sol[i];
    fprintf(fout,"%d\n",s);   
    fclose(fin);
    fclose(fout);
    return 0;
}