UVa 778 - Recording a tape

// UVa 778 - Recording a tape
#include <iostream>
#include <map>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

struct Song {
	string l;
	int len;
};

vector<int> readCassetteLengths(const string& line, int& max_len) {
	istringstream strm(line);
	int len;
	vector<int> lens;
	while (strm >> len) {
		len *= 30;
		lens.push_back(len);
		if (len > max_len)
			max_len = len;
	}
	return lens;
}

vector<Song> readSongLengths(int& songs_total) {
	vector<Song> songs;
	string line;
	getline(cin, line);
	while (line != "%") {
		istringstream strm(line);
		string w;
		strm >> w;
		int mins = 0;
		for (unsigned i = 0; i < w.length(); i++)
			if (w[i] >= '0' && w[i] <= '9')
				mins = mins * 10 + w[i] - '0';
		strm >> w;
		int secs = 0;
		for (unsigned i = 0; i < w.length(); i++)
			if (w[i] >= '0' && w[i] <= '9')
				secs = secs * 10 + w[i] - '0';
		Song e = { line, mins * 60 + secs };
		songs.push_back(e);
		songs_total += e.len;
		getline(cin, line);
	}
	return songs;
}

void updateClosests(const vector<int>& lens, int new_gen, vector<int>& closest_to) {
	for (int i = 0; i < lens.size(); i++) {
		if (closest_to[i] < new_gen && new_gen <= lens[i]) {
			closest_to[i] = new_gen;
		}
	}
}

map<int, int> knapsack(int capacity, const vector<Song>& items, const vector<int>& lens, vector<int>& closest_to) {
	map<int, int> generated;
	generated[0] = -1;
	for (int i = 0; i < items.size(); i++) {
		int item = items[i].len;
		vector<int> new_gens;
		for (map<int, int>::iterator it = generated.begin(); it != generated.end(); ++it) {
			int new_gen = it->first + item;
			if (generated.count(new_gen) == 0)
				new_gens.push_back(new_gen);
		}
		for (vector<int>::iterator it = new_gens.begin(); it != new_gens.end(); ++it) {
			int new_gen = *it;
			if (generated.count(new_gen) == 0) {
				generated[new_gen] = i + 1;
				updateClosests(lens, new_gen, closest_to);
			}
		}
	}
	return generated;
}

int getSmallestPossibleLength(const vector<int>& closest_to, const vector<int>& lens, int& songs_total) {
	int smallest_possible_length = -1;
	for (int i = 0; i < closest_to.size(); i++) {
		if (songs_total - closest_to[i] <= lens[i] && (smallest_possible_length == -1 || lens[i] < lens[smallest_possible_length]))
			smallest_possible_length = i;
	}
	return smallest_possible_length;
}

vector<bool> reconstruct(int length, map<int, int>& sack, const vector<Song>& songs) {
	vector<bool> used(songs.size());
	while (length > 0) {
		int item_index = sack[length] - 1;
		used[item_index] = true;
		length -= songs[item_index].len;
	}
	return used;
}

void print_side(const vector<bool>& sides, bool this_side, const vector<Song>& songs) {
	for (int i = 0; i < sides.size(); i++) {
		if (sides[i] == this_side)
			cout << songs[i].l << endl;
	}
}

int main() {
	string line;
	while (getline(cin, line)) {
		istringstream strm(line);

		int max_len = -1;
		vector<int> lens = readCassetteLengths(line, max_len);

		int songs_total = 0;
		vector<Song> songs = readSongLengths(songs_total);

		vector<int> closest_to(lens.size());
		map<int, int> sack = knapsack(max_len >> 1, songs, lens, closest_to);

		int smallest_possible_length = getSmallestPossibleLength(closest_to, lens, songs_total);
		cout << lens[smallest_possible_length] / 30 << endl;

		vector<bool> sides = reconstruct(closest_to[smallest_possible_length], sack, songs);
		cout << "Side A" << endl;
		print_side(sides, true, songs);
		cout << "Side B" << endl;
		print_side(sides, false, songs);

		cout << '%' << endl;

	}

	return 0;
}