Cod sursa(job #827070)

Utilizator moscaliuc_ovidiuMoscaliuc Ovidiu moscaliuc_ovidiu Data 1 decembrie 2012 16:29:27
Problema Ghiozdan Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <string.h>
#include <list>

#define MAX_N ((const unsigned int)20000)
#define MAX_G ((const unsigned int)75000)
#define INFINITE ((const unsigned int)-1000000)

typedef std::list<int>		Vector;

int N, G;

int w[MAX_N];
unsigned int min[MAX_G];

Vector sol[MAX_G];
Vector solFin;

unsigned int nr = INFINITE;
unsigned int weight = 0;

int main()
{
	std::ifstream fin("ghiozdan.in");
	std::ofstream fout("ghiozdan.out");

	fin>>N>>G;

	for (int i = 0; i < N; ++ i)
		fin>>w[i];

	memset(min, INFINITE, sizeof(int) * MAX_G);

	min[0] = 0;

	for (int i = 0; i < N; ++ i)
	{
		for (int j = G - w[i]; j >= 0; -- j)
		{
			if (min[j + w[i]] > min[j] + 1)
			{
				min[j + w[i]] = min[j] + 1;
				sol[j + w[i]] = sol[j];
				sol[j + w[i]].push_back(i);

				if (j + w[i] >= weight)
				{
					if (weight != j + w[i])
						weight = j + w[i];

					if (nr != min[j + w[i]])
					{
						nr = min[j + w[i]];
						solFin = sol[j + w[i]];
					}
				}
			}
		}
	}

	fout<<weight<<" "<<nr<<'\n';

	for (Vector::iterator itBegin = solFin.begin(); itBegin != solFin.end(); ++ itBegin)
		fout<<*itBegin<<'\n';

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

	return 0;
}