Cod sursa(job #438362)

Utilizator nc3bCatalin nc3b Data 10 aprilie 2010 18:17:04
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

struct gutuie {
	int height;
	int weight;
};

bool compare_gutui(gutuie g1, gutuie g2)
{
	return(g1.weight > g2.weight);
}

int main()
{
	ifstream fin;
	ofstream fout;
	
	fin.open("gutui.in", ios::in);
	fout.open("gutui.out", ios::out);

	if( !fin.is_open() || !fout.is_open() )
	{
		cerr << "Unul din fisiere nu a putut fi deschis \n";
		return(1);
	}

	int N = 0;
	int H = 0;
	int U = 0;

	fin >> N;
	fin >> H;
	fin >> U;

//	cout << N << " " << H << " " << U << endl;

	list <gutuie> gutui;
	int current_height = H;

	for(int i = 0; i < N; i ++)
	{
		gutuie g;
		fin >> g.height;
		fin >> g.weight;

		gutui.push_back(g);
	}

	gutui.sort(compare_gutui);
	char * result = new char[N];
	memset(result, 0, N);

	int credit		= 0;
	int gweight		= 0;

	for(list <gutuie>::iterator it = gutui.begin();
		(it != gutui.end()) && 0 != current_height;
		it ++)
	{
		credit = (current_height - (*it).height) / U;
//		cout << (*it).height << " : " << (*it).weight << " credit: " << credit << endl;
		
		if(credit < 0)
		{
			continue;
		}
		credit = min (credit, N - 1);

		for(int i = credit; i>= 0; i --)
		{
			if(0 == result[i])
			{
				//nu e nici o gutuie pe pozitia aia
				//culegem gutuia noastra
				result[i] = 1;
				gweight += (*it).weight;
				break;		//este esential
			}
		}
	}

	fout << gweight;

	fin.close();
	fout.close();

	return(0);
}