Cod sursa(job #439861)

Utilizator cyberClaudia Cardei cyber Data 11 aprilie 2010 20:00:46
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.31 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NMAX 100001

typedef struct {
        int h, g, r;
} gutuie;

int compar(const void *a, const void *b) {
    
    gutuie x, y;
    
    x = *(gutuie *) a;
    y = *(gutuie *) b;
    
    if (x.r > y.r) return 1;
    if (x.r < y.r) return -1;
    
    return x.g - y.g;
}

int main() {
        
    gutuie G[NMAX];
    int V[NMAX];
    int N, HMAX, U, GMAX, i, DIF;
    
    freopen("gutui.in", "rt", stdin);
    freopen("gutui.out", "wt", stdout);
    
    scanf("%d %d %d", &N, &HMAX, &U);
    
    for (i = 0 ; i <  N; i++) {
        scanf("%d %d", &G[i].h, &G[i].g);
        G[i].r = (HMAX - G[i].h) / U;
    }
    
    qsort(G, N, sizeof(G[1]), compar);
    memset(V, 0, sizeof(V));
    
    /*for(i = 0 ; i < N; i++)
          printf("%d ", G[i].r);*/
    
    for (i = 0, GMAX = 0; i <  N - 1; i++)
        if (G[i].r != G[i+1].r) {
           GMAX += G[i].g;
           V[i] = 1;
        }
        
    GMAX += G[N-1].g;
    V[N-1] = 1;
    
    DIF = G[0].r;
    for (i = 0; i < N && DIF; i++)
        if (V[i] == 0) {
           GMAX += G[i].g;
           V[i] = 1;
           DIF--;
        }  
           
    printf("\n%d\n", GMAX);
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}