Cod sursa(job #463704)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 17 iunie 2010 12:10:31
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.83 kb
//TUDOSE VLAD 323CA - GUTUI
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

//structura in care retin inaltimea,greutatea 
//unei gutui si cate gutui mai pot fi culese 
//inainte ca inaltimea gutuii sa devina >H

typedef struct{
	long weight;
	long height;
	long lifetime;
}quince;

//functie de comparare a inaltimilor
//folosita la sortare
bool compare (quince i,quince j) 
{ 
	return (i.height>j.height); 
}

//functie care returneza solutia problemei
long Quinces()
{
	long N,H,U,total_weight=0,sum=0,last;
	int i;
	//CITIREA
	FILE *in=fopen("gutui.in","r");
	fscanf(in,"%ld %ld %ld\n",&N,&H,&U);
	vector<quince> q(N);
	priority_queue<long> pq;

	for(i=0;i<N;i++)
	{
		fscanf(in,"%ld %ld\n",&q[i].height,&q[i].weight);
		q[i].lifetime=(H-q[i].height)/U+1;
		total_weight+=q[i].weight;
	}
	fclose(in);
	//daca U este 0 returnam suma greutatilor
	//tuturor gutuilor
	if(!U)
	return total_weight;
	sort(q.begin(),q.end(),compare);
	
	//numarul de gutui culese va fi egal cu
	//lifetime-ul gutuii cu inaltimea cea mai mica
	last=q.back().lifetime;
	
	while((q.size() or pq.size())and last)
	{
		//daca avem ceva in coada de prioritati
		//scoatem afara o gutuie iar greutatea ei
		//o adaugam la suma finala
		if(pq.size())
		{
			sum+=pq.top();
			pq.pop();
			last--;
		}
		//daca nu,trecem la urmatoarea gutuie
		else
		{
			last=q.back().lifetime;
		}
		//daca mai avem gutui neparcurse si putem ajunge la ele
		//le adaugam in coada de prioritati
		while(q.size() and q.back().lifetime>=last)
		{
			pq.push(q.back().weight);
			q.pop_back();
		}                       
	}
	return sum;
}

int main ()
{
	//Scrierea solutiei in fisier
	FILE *out=fopen("gutui.out","w");
	fprintf(out,"%ld",Quinces());
	fclose(out);  
	return 0;
}