Cod sursa(job #442002)

Utilizator emilia.ciobanuCiobanu Emilia Maria Silvia emilia.ciobanu Data 13 aprilie 2010 19:35:05
Problema Gutui Scor 20
Compilator cpp Status done
Runda teme_upb Marime 2.62 kb
#include<fstream>
#include<cstdlib>
#include<climits>
#include<vector>
#include<algorithm>

#define IN "gutui.in"
#define OUT "gutui.out"

using namespace std;

typedef struct
{
	unsigned long h;
	unsigned long w;
	unsigned long l;
} GUTUIE;

bool cmph ( GUTUIE i, GUTUIE j)
{
	return i.h > j.h;
}

bool cmpw ( GUTUIE i, GUTUIE j)
{
	return i.w < j.w;
}

int main (int argc, char **argv)
{
	FILE *fin  = fopen (IN, "r");
	FILE *fout = fopen (OUT, "w");
	int i, aux;
	int N;
	unsigned long H, U;
	unsigned long G = 0;
	fscanf (fin, "%d%lu%lu", &N, &H, &U);

	vector <GUTUIE> g, Heap;
	make_heap (Heap.begin(), Heap.end(), cmpw);

	for (i = 0; i < N; ++i)
	{
		GUTUIE a;
		fscanf(fin, "%lu%lu", &a.h, &a.w);
		if (a.h > H)
		{
			aux = 1;
			continue;
		}
		a.l = a.h/U+(a.h%U == 0?0:1);
		g.push_back(a);
	}

	sort (g.begin(), g.end(), cmph);
/*
	for ( i = 0; i < (int)g.size() ;++i)
		printf("Gutuie :\tinaltime: %d\t greutate: %d\t level: %d\n", g[i].h, g[i].w, g[i].l);
	printf("\n");
*/
	if ( aux == 1)
	N = (int)g.size();
	unsigned long current = g[N-1].l;
//	printf("CURRENT : %d\n", current);
	Heap.push_back (g[N-1]);
	push_heap (Heap.begin(), Heap.end(), cmpw);

	for (i = N-2; i >= 0; --i)
	{
//		printf("--------PASUL %d-------\n", N-i-1);
//		printf("Gutuie :\tinaltime: %d\t greutate: %d\t level: %d\n", g[i].h, g[i].w, g[i].l);
//		printf("\t g[i].l %d, g[i+1].l %d\n", g[i].l, g[i+1].l);
		if (g[i].l != g[i+1].l)
		{
//			printf("\tDIFERENTA DE NIVEL 1\n,\tcurrent %d\n", current);
			for (; current < g[i].l ; current++)
			{
//				printf("\t\tCurrent %d\n", current);
				if (Heap.size())
				{
					G += Heap.front().w;
//					printf("\t\t\t SCOT GUTUIA: %d %d %d\n", Heap.front().h, Heap.front().w, Heap.front().l);
					pop_heap (Heap.begin(), Heap.end(), cmpw);
					Heap.pop_back();
				}
			}
		}
//		printf("\t PUN GUTUI\n");
		Heap.push_back (g[i]);
		push_heap (Heap.begin(), Heap.end(), cmpw);
	}

/*	printf("AM IESIT DIN PRIMUL FOR; HEAP:\n");
	for ( i = 0 ; i < (int)Heap.size(); ++i)
		printf("\t%d %d %d\n", Heap[i].h, Heap[i].w, Heap[i].l);
	printf("current %d\n", current);

	// Daca mai raman gutui de cules
*/	for ( ; current < H/U + 1 && Heap.size() ; ++current)
	{
//		printf("Mai am gutui de adaugat (current %d)\n", current);
		G += Heap.front().w;
		pop_heap (Heap.begin(), Heap.end(), cmpw);
		Heap.pop_back();
	}

/*	for ( i = 0 ; i < (int)Heap.size(); ++i)
		printf("\t%d %d %d\n", Heap[i].h, Heap[i].w, Heap[i].l);
	for (i = 0 ; i < Heap.size(); ++i)
		fprintf (fout, "GUTUIE %d %d\n", Heap[i].w, Heap[i].h);
	fprintf (fout, "\n");*/
	//printf("\n%ld\n", G);
	fprintf (fout, "%lu\n", G);

	fclose (fin);
	fclose (fout);

	return 0;
}