Cod sursa(job #441543)

Utilizator cyberClaudia Cardei cyber Data 12 aprilie 2010 23:04:53
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.62 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];
    int N, HMAX, U, GMAX, i, T;
    priority_queue<int> heap;
    
    freopen("gutui.in", "rt", stdin);
    freopen("gutui.out", "wt", stdout);
    
    scanf("%d %d %d", &N, &HMAX, &U);
    
    /* citirea datelor */
    
    for (i = 0 ; i <  N; i++) {
        scanf("%d %d", &G[i].h, &G[i].g);
        G[i].r = (HMAX - G[i].h) / U;
    }
    
    /* sortarea descrescatoare dupa timpii maximi de cules pentru fiecare gutuie */
    
    qsort(G, N, sizeof(G[1]), compar);
    
    /* greedy - la fiecare pas se introduc in heap greutatile gutuilor
    cu timpul maxim egal cu timpul curent, si se extrage maximul */
    
    for (i = 0, GMAX = 0, T = G[0].r; i < N && T >= 0; T--) {
        
        while (G[i].r == T && i < N) {
              heap.push(G[i].g);
              i++;
        }
        
        if (!heap.empty()) {       
           GMAX += heap.top();
           heap.pop();
        }
    }
    
    /* daca s-au epuizat gutuile, dar timpul ne permite sa mai culegem,
    atunci actualizam greutatea maxima */
    
    while (T >=0 && !heap.empty()) {
          GMAX += heap.top();
          heap.pop();
          T--;
    } 
           
    printf("%d\n", GMAX);
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}