Cod sursa(job #727910)

Utilizator fhandreiAndrei Hareza fhandrei Data 28 martie 2012 12:53:12
Problema Zebughil Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
//Include
#include <fstream>
#include <set>
using namespace std;

//Clase
class descrescator
{
	public:
	bool operator() (int a, int b)
	{	return (a>b);	}
};

//Variabile
ifstream in("zebughil.in");
ofstream out("zebughil.out");

int teste = 3;
int n, capacitate;
int citit;
int dimensiuneRamasa;
int nrCamioane;

multiset<int, descrescator > blocuri;
multiset<int, descrescator >::iterator it, end, bound;

//Main
int main()
{
	while(teste--)
	{
		in >> n >> capacitate;
		for(int i=1 ; i<=n ; ++i)
		{
			in >> citit;
			blocuri.insert(citit);
		}
		
		end = blocuri.end();
		for(nrCamioane=0 ; !blocuri.empty() ; ++nrCamioane)
		{
			dimensiuneRamasa = capacitate;
			while( (bound = blocuri.lower_bound(dimensiuneRamasa)) != end)
			{
				dimensiuneRamasa -= *bound;
				blocuri.erase(bound);
			}
		}
		
		out << nrCamioane << '\n';
	}
	
	
	in.close();
	out.close();
	return 0;
}