Cod sursa(job #442242)

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

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

using namespace std;

typedef struct
{
	int h;
	int w;
	int l;
} GUTUIE;

bool cmph (GUTUIE, GUTUIE);

bool cmpw (GUTUIE, GUTUIE);

int main (int argc, char **argv)
{
	FILE *fin  = fopen (IN, "r");
	FILE *fout = fopen (OUT, "w");
	vector <GUTUIE> g, Heap;
	unsigned long G = 0;
	int i;
	int N;
	int H, U, current;
	char aux, buffer[DIM], *pb;

	fscanf (fin, "%d%d%d", &N, &H, &U);
	make_heap (Heap.begin(), Heap.end(), cmpw);

	/* Citire selectiva, in cazul in care o parte din gutui sunt
	 * la o inaltime > H
	 */
	/*
	for (i = 0; i < N; ++i)
	{
		GUTUIE a;
		fscanf(fin, "%d%d", &a.h, &a.w);
		if (a.h > H)
		{
			aux = 1;
			continue;
		}
		a.l = (H - a.h)/U + 1;
		g.push_back(a);
	}*/

	GUTUIE a;

	fread (buffer, sizeof(char), DIM, fin);
	pb = strtok (buffer, " ");
	a.h = atoi (pb);
	pb = strtok (0, "\n");
	a.w = atoi (pb);
	if ( a.h > H )
		aux = 1;
	a.l = (H - a.h)/U + 1;
	g.push_back (a);

	for (i = 1; i < N ; ++i)
	{
		pb = strtok ( 0, " ");
		a.h = atoi (pb);
		pb = strtok ( 0, "\n");
		a.w = atoi (pb);
		if ( a.h > H )
			aux = 1;
		a.l = (H - a.h)/U + 1;
		g.push_back (a);
	}

	if ( aux == 1)
		N = (int)g.size();

	/*printf("%d %d %d\n", N, H, U);
	for ( i = 0; i < N ; ++i)
		printf("%d %d %d\n", g[i].w, g[i].h, g[i].l);
*/
	/* Daca am gasit astfel de gutui, nu am nevoie sa lucrez cu ele => actualizez N */
	if ( aux == 1)
		N = (int)g.size();

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

	for (i = 0; i < N; ++i)
	{
		if (i == 0)
		{
			current = g[i].l;
			Heap.push_back (g[0]);
			push_heap (Heap.begin(), Heap.end(), cmpw);
			continue;
		}

		if (g[i].l != g[i-1].l)
		{
			while (current > g[i].l)
			{
				current--;
				if (Heap.size())
				{
					G += Heap.front().w;
					pop_heap (Heap.begin(), Heap.end(), cmpw);
					Heap.pop_back();
				}
				else break;
			}
		}
		Heap.push_back (g[i]);
		push_heap (Heap.begin(), Heap.end(), cmpw);
	}

	while (current > 0 && Heap.size())
	{
		G += Heap.front().w;
		pop_heap (Heap.begin(), Heap.end(), cmpw);
		Heap.pop_back();
		current--;
	}

	fprintf (fout, "%lu\n", G);

	fclose (fin);
	fclose (fout);

	return 0;
}

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

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