Cod sursa(job #441031)

Utilizator cyberClaudia Cardei cyber Data 12 aprilie 2010 18:47:41
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.56 kb
#include <stdio.h>
#include <stdlib.h>
#include <queue>

using namespace std; 

#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;
    
    return y.r - x.r;
}

int main() {
        
    gutuie G[NMAX];
    long long N, HMAX, U, GMAX, i, TMAX;
    priority_queue<long long> heap;
    
    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);
    
    for (i = 0, GMAX = 0, TMAX = G[0].r; i < N && TMAX >= 0; TMAX--) {
        
        //printf("TMAX: %d\n", TMAX);
        if (G[i].r != TMAX) i++;
        
        while (G[i].r == TMAX && i < N) {
              heap.push(G[i].g);
          //    printf("push: %d", G[i].g);
              i++;
        }
        
        if (!heap.empty()) {
           //printf("pop: %d", heap.top());       
           GMAX += heap.top();
           heap.pop();
        }
        //printf("\n%d\n", i);
    }
    

    //printf("\nTMAX fin: %d, %d",TMAX, heap.empty());
     
    while (TMAX >=0 && !heap.empty()) {
      //    printf("ent");
          GMAX += heap.top();
          heap.pop();
          TMAX--;
    } 
           
    printf("%d\n", GMAX);
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}