Cod sursa(job #462981)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 14 iunie 2010 12:08:56
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.91 kb
/**
 * NUME: CARBUNE VICTOR
 * GRUPA: 325 CA
 * PROBLEMA: GUTUI
 *
 */
#include <vector>
#include <stdio.h>
#include <algorithm>
#define N 100000

using namespace std;

typedef struct {
	unsigned long w, h, pos;
} quince;

unsigned long n, hmax, u;
vector<quince> v, heap;

void read() {
	unsigned int i;

	scanf("%lu %lu %lu", &n, &hmax, &u);

	for ( i = 0; i < n; i++ ) {
		quince e;
		scanf("%lu %lu", &e.h, &e.w);
		e.pos = (hmax - e.h)/u + 1;

		v.insert(v.end(), e);
	}
}

/* Compararea gutuilor dupa greutate */
bool quinceCmpWeight (const quince q1, const quince q2) {
	if (q1.w < q2.w)
		return true;
	return false;
}

/* Compararea gutuilor dupa nivel / pozitie */
bool quinceCmpPos (const quince q1, const quince q2) {
	if (q1.pos > q2.pos)
		return true;
	
	return false;
}

int main() {
	unsigned long gmax = 0, minPos, i;
	freopen("gutui.in", "r", stdin);	
	freopen("gutui.out", "w", stdout);

	read();

	//complexitate O(NlogN) -- sortare
	sort(v.begin(), v.end(), quinceCmpPos);

	minPos = v[0].pos;
	heap.push_back(v[0]);
	push_heap(heap.begin(), heap.end(), quinceCmpWeight);
	
	//complexitate O(NlogN) -- for + inserare in heap
	for ( i = 1; i < n; i++ ) { //O(N)
		//daca se intalneste o gutuie cu un nivel diferit de cel curent
		//se scot din heap un numar de gutui egale cu diferenta de nivel
		if ( v[i].pos < v[i-1].pos )
			while ( minPos > v[i].pos ) {
				if(heap.size()) {
					gmax += heap.front().w;

					pop_heap(heap.begin(), heap.end(), quinceCmpWeight); //O(logN)
					heap.pop_back();
				}
				minPos--;
			}
		//se insereaza gutuia in heap
		heap.push_back(v[i]);
		push_heap(heap.begin(), heap.end(), quinceCmpWeight); //O(logN)
	}

	//daca heap-ul nu este gol, si mai sunt pasi disponibili, se scot din heap
	while ( minPos > 0 && heap.size() ) {
		gmax += heap.front().w;
		
		pop_heap(heap.begin(), heap.end(), quinceCmpWeight);//O(logN)
		heap.pop_back();
		
		minPos--;
	}

	printf("%lu\n", gmax);

	return 0;
}