Cod sursa(job #526633)

Utilizator ucc_5Usurelu Catalin ucc_5 Data 28 ianuarie 2011 22:36:20
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
//pana la un timp t adaugam toate solutiile optime care respecta conditia timpului 
//ex: toate solutiile pot fi doar din timp 0 spre exemplu
#include <fstream>
#define nmax 100002
using namespace std;

ifstream f("lupu.in");
ofstream g("lupu.out");


struct sheep {int dist,lana,timp; } oaie[nmax],heap[nmax]; //timp-numaru de alegeri pana cand oaia nu mai poate fi aleasa
long long sol;
int n,x,l,tmax=-1,heap_size;

void citire ()
{
	f>>n>>x>>l;
	for (int i=1; i<=n; i++)
	{
		f>>oaie[i].dist>>oaie[i].lana;
		oaie[i].timp=(x-oaie[i].dist)/l;
		tmax=max(tmax,oaie[i].timp);
	}
	f.close ();
}

bool cmp1 (sheep first, sheep second)
{
	return first.timp>second.timp;
}

bool cmp2 (sheep first, sheep second)
{
	return first.lana<second.lana;
}

void alege_oi ()
{
	int i=1;
 	sort (oaie+1,oaie+n+1,cmp1);
	for (int timp=tmax; timp>=0 && i<=n; timp--)
	{
		while (oaie[i].timp==timp && i<=n)
		{
			heap[++heap_size]=oaie[i];
			push_heap (heap+1,heap+heap_size+1,cmp2);
			i++;
		}
		if (heap_size)
		{
			sol+=heap[1].lana;
			pop_heap (heap+1,heap+heap_size+1,cmp2);
			heap_size--;
		}
	}
}

void afisare ()
{
	g<<sol;
	g.close ();
}
	
int main ()
{
	citire ();
	alege_oi (); 
	afisare ();
	return 0;
}