Cod sursa(job #441792)

Utilizator emilia.ciobanuCiobanu Emilia Maria Silvia emilia.ciobanu Data 13 aprilie 2010 13:15:25
Problema Gutui Scor 90
Compilator cpp Status done
Runda teme_upb Marime 1.61 kb
#include<fstream>
#include<cstdlib>
#include<climits>
#include<vector>
#include<algorithm>

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

using namespace std;

typedef struct
{
	int h;
	int w;
	int 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;
	int N, H, U;
	int G = 0;
	fscanf (fin, "%d%d%d", &N, &H, &U);

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

	for (i = 0; i < N; ++i)
	{
		fscanf(fin, "%d%d", &X, &Y);
		GUTUIE a;
		a.w = Y;
		a.h = X;
		a.l = (H - X)/U + 1;
		g.push_back(a);
	}

	sort (g.begin(), g.end(), cmph);

	/*
	for ( i = 0; i < N ;++i)
		printf("Gutuie :\tinaltime: %d\t greutate: %d\t level: %d\n", g[i].h, g[i].w, g[i].l);
	printf("\n");
*/

	int current = g[0].l;
	Heap.push_back (g[0]);
	push_heap (Heap.begin(), Heap.end(), cmpw);

	for (i = 1; i < N; ++i)
	{
		if (g[i].l < g[i-1].l)
		{
			for (; current > g[i].l && Heap.size() ; --current)
			{
				G += Heap.front().w;
				pop_heap (Heap.begin(), Heap.end(), cmpw);
				Heap.pop_back();
			}
		}
		Heap.push_back (g[i]);
		push_heap (Heap.begin(), Heap.end(), cmpw);
	}

	// Daca mai raman gutui de cules
	for ( ; current > 0 && Heap.size() ; --current)
	{
		G += Heap.front().w;
		pop_heap (Heap.begin(), Heap.end(), cmpw);
		Heap.pop_back();
	}

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

	fclose (fin);
	fclose (fout);

	return 0;
}