Cod sursa(job #441991)

Utilizator emilia.ciobanuCiobanu Emilia Maria Silvia emilia.ciobanu Data 13 aprilie 2010 19:20:13
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.58 kb
#include <stdio.h>
#include <vector>
#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);
	}
}

void print() {
	unsigned int i;
	
	for ( i = 0; i < v.size(); i++ )
		printf("%lu %lu %lu\n", v[i].h, v[i].w, v[i].pos);
}

bool quinceCmpWeight (const quince q1, const quince q2) {
	if (q1.w < q2.w)
		return true;
	return false;
}

bool quinceCmpHeight (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();

	sort(v.begin(), v.end(), quinceCmpHeight);
	
/*	for (i = 0; i < v.size(); ++i)
		printf("Gutuie :\tinaltime: %lu\t greutate: %lu\t level: %lu\n", v[i].h, v[i].w, v[i].pos);*/
	make_heap(heap.begin(), heap.end(), quinceCmpWeight);

	minPos = v[0].pos;
	heap.insert(heap.end(), v[0]);
	push_heap(heap.begin(), heap.end(), quinceCmpWeight);

//	printf("CURRENT %lu\n", minPos);

	for ( i = 1; i < n; ++i ) 
	{
//		printf("--------PASUL %lu-------\n", i);
//		printf("Gutuie :\tinaltime: %lu\t greutate: %lu\t level: %lu\n", v[i].h, v[i].w, v[i].pos);
//		printf("\t g[i].l %lu, g[i+1].l %lu\n", v[i].pos, v[i-1].pos);

		if ( v[i].pos != v[i-1].pos )
		{
//			printf("\tDIFERENTA DE NIVEL 1\n,\tcurrent %lu\n", minPos);
			for ( ; minPos > v[i].pos; --minPos )
			{
//				printf("\t\tCurrent %lu\n", minPos);
				if(heap.size()) 
				{
//					printf("\t\t\t SCOT GUTUIA: %lu %lu %lu\n", heap.front().h, heap.front().w, heap.front().pos);
					gmax += heap.front().w;
					pop_heap(heap.begin(), heap.end(), quinceCmpWeight);
					heap.pop_back();
				}
			}
		}
//		printf("\t PUN GUTUI\n");

		heap.insert(heap.end(), v[i]);
		push_heap(heap.begin(), heap.end(), quinceCmpWeight);
	}
//	printf("AM IESIT DIN PRIMUL FOR; HEAP:\n");
//	for ( i = 0 ; i < heap.size(); ++i)
//		printf("\t%lu %lu %lu\n", heap[i].h, heap[i].w, heap[i].pos);
//	printf("current %lu\n", minPos);
	
	for ( ; minPos > 0 && heap.size(); --minPos ) 
	{
	
//		printf("Mai am gutui de adaugat (current %lu)\n", minPos);
		gmax += heap.front().w;
		pop_heap(heap.begin(), heap.end(), quinceCmpWeight);
		heap.pop_back();
	}

/*	for ( i = 0 ; i < heap.size(); ++i)
		printf("\t%lu %lu %lu\n", heap[i].h, heap[i].w, heap[i].pos);
	printf("\n");
*/
	
	printf("%lu\n", gmax);

	return 0;
}