Pagini recente » Cod sursa (job #1108128) | Cod sursa (job #1272618) | Cod sursa (job #3187570) | Cod sursa (job #3195632) | Cod sursa (job #463028)
Cod sursa(job #463028)
// 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);
bool
dupaInaltime(pair < uint32_t, uint32_t > i, pair < uint32_t, uint32_t > j);
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;
for (i = 0; i < heapAux.size(); i++)
sum += heapAux[i].greutate;
fout << sum;
return 0;
}
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);
}