Cod sursa(job #463590)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 16 iunie 2010 14:51:29
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.68 kb
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

//structura unei gutui
struct Gutui{
	long h;	//inaltime
	long w;	//greutate
	int mark;	//culeasa sau nu
	bool operator() (Gutui a, Gutui b) { if (a.h==b.h) return (a.w<b.w); return (a.h<b.h); } //functie de comparare dupa inaltime si greutate in cazul in care inaltimile sunt egale
}gutui;

bool weigthcompare (Gutui a, Gutui b) { return (a.w < b.w);}	//functie de comparare dupa greutate

int main(){
	long n,h,u,u1=0,umax=0;
	
	ifstream fin ("gutui.in");
	ofstream fout ("gutui.out");
	fin>>n>>h>>u;
	Gutui max;
	vector<Gutui> g(n);	
	for (long i=0; i<n; i++)
		fin>>g[i].h>>g[i].w;
	for (long i=0; i<n; i++)
		{
		
		g[i].mark=0;
		}
	
	//sortare crescatoare dupa inaltimi
	sort(g.begin(),g.end(),gutui);

	//inversarea vectorului
	Gutui aux;
	for (long i=0; i<n/2; i++)
		{
		aux=g[i];
		g[i]=g[n-i-1];
		g[n-i-1]=aux;
		}
	
	long i=0;
	while (i<n)
		{
		//verificam daca gutuia se poate culege
		if (g[i].h+u1 < h && g[i].mark == 0)
			{	
			//marim pasul si verificam daca urmatorul pas va fi ultimul in care gutuia i va putea fi culeasa
			u1+=u;
			if (g[i].h+u1 == h)
				{
				umax+=g[i].w;
				g[i].mark=1;
				i++;
				}

			//daca nu, atunci gasim gutuia cu greutate maxima si o culegem
			else
				{
				max= *max_element(g.begin()+i,g.end(),weigthcompare);
				for (long j=i; j<n; j++)
					if (g[j].w==max.w && g[j].mark==0)
						{
						umax+=g[j].w;
						g[j].mark=1;
						}
				}
			}
			else 
				//in cazul in care se depaseste h se marcheaza gutuia si se trece la urmatorul pas
				{
				g[i].mark=1;
				i++;
				}			
		}
	
	//afisare si inchidere de fisiere
	fout<<umax<<endl;
	fin.close();
	fout.close();
	return 0;
}