Cod sursa(job #438798)

Utilizator vdobrotaDobrota Valentin Eugen vdobrota Data 11 aprilie 2010 00:39:43
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.89 kb
// Dobrota Valentin-Eugen, 324CA, PA, Tema1, Prob2 - Gutui, 2009-2010
#include<fstream>
#include<vector>
#include<algorithm>
#include<utility>
#include<sys/types.h>
#define inaltime first
#define greutate second
using namespace std;

bool
dupaGreutate(pair < uint32_t, uint32_t > i, pair < uint32_t, uint32_t > j)
{
    return (i.greutate > j.greutate);
}

bool
dupaInaltime(pair < uint32_t, uint32_t > i, pair < uint32_t, uint32_t > j)
{
    return (i.inaltime > j.inaltime);
}

int main()
{
    // Declaratii si date de intrare
    uint32_t k, j, h, n, u, sum, i;
    ifstream fin("gutui.in", ios::in);
    ofstream fout("gutui.out", ios::out);
    vector < pair < uint32_t, uint32_t > >gutui;
    vector < pair < uint32_t, uint32_t > >heapAux;    
    // Citirea
    fin >> n >> h >> u;
    for (i = 0; i < n; i++) {
		fin >> j >> k;
		gutui.push_back(make_pair(j, k));
    }
    // De la cea mai inalta gutuie la cea mai joasa
    sort(gutui.begin(), gutui.end(), dupaInaltime);
    heapAux.push_back(gutui[0]);
    // Iau gutuile in ordine
    for (i = 1; i < n; i++) {
		// E bine sa facem schimb intre gutuia i si cea mai usoara din heap?
		if (heapAux.size() == ((h - gutui[i].inaltime) / u + 1 )
			&& heapAux.front().greutate < gutui[i].greutate) {
			pop_heap(heapAux.begin(), heapAux.end(), dupaGreutate);
			heapAux.pop_back();
			heapAux.push_back(make_pair(gutui[i].inaltime, gutui[i].greutate));
			push_heap(heapAux.begin(), heapAux.end(), dupaGreutate);
		}
		// Sau putem doar sa punem gutuia in heap fara sa scoatem nimic        
		else if (heapAux.size() != (1 + (h - gutui[i].inaltime) / u)) {
			heapAux.push_back(make_pair(gutui[i].inaltime, gutui[i].greutate));
			push_heap(heapAux.begin(), heapAux.end(), dupaGreutate);
		}
    }
    sum = 0;
    // Raspunsul este suma greutatilor gutuilor din heap    
    for (i = 0; i < heapAux.size(); i++)
		sum += heapAux[i].greutate;
    fout << sum;
    return 0;
}