Cod sursa(job #1258589)

Utilizator devilz05Orzan Alexandru devilz05 Data 9 noiembrie 2014 00:48:59
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.24 kb
#include <stdio.h>
#include <algorithm>
#include <queue>

using namespace std;

struct gutui
{
    int w, h;
};

bool gsortCond(gutui g1, gutui g2)
{
    if (g1.h == g2.h)
        return g1.w > g2.w;
    else
        return g1.h > g2.h;
}

void readData(gutui **gParam, int *N, int *H, int *U)
{
    gutui *g = NULL;;
    int i;
    
    scanf("%i%i%i", N, H, U);
    g = new gutui[*N];
    
    for (i=0; i<*N; ++i)
    {
        scanf("%i%i", &g[i].h, &g[i].w);
        if (g[i].h <= *H)
            g[i].h = (*H-g[i].h)/(*U);
        else
        {
            --i; --(*N);
        }
    }
    
    sort(g, g+*N, gsortCond);
    *gParam = g;
}

void gSolve(gutui *g, int N, int H, int U, long long *w)
{
    int i, j;
    priority_queue<int> Q;
    
    for (i=g[0].h, *w=j=0; i>=0; --i)
    {
        for (; g[j].h==i && j<N; ++j)
            Q.push(g[j].w);
        if (Q.empty()) continue;
        *w+=Q.top();
        Q.pop();
    }
}

int main()
{
    gutui *g = NULL;
    int H, U, N;
    long long w;
    
    freopen("gutui.in", "r", stdin);
    freopen("gutui.out", "w", stdout);
    
    readData(&g, &N, &H, &U);
    gSolve(g, N, H, U, &w);
    printf("%lli", w);
    
    return 0;
}