UVa 11782 - Optimal Cut

#include <stdio.h>
#include <string.h>

#define TWO_TO_THE_21 2097152
#define MAX_TO_SELECT 20

int tree_height, cut_limit, tree[TWO_TO_THE_21], T[TWO_TO_THE_21][MAX_TO_SELECT + 1], oo;
bool calculated[TWO_TO_THE_21][MAX_TO_SELECT + 1];

void readInPreOrder(int index, int depth) {
	scanf("%d", &tree[index]);
	if (depth < tree_height) {
		readInPreOrder(index * 2 + 1, depth + 1);
		readInPreOrder(index * 2 + 2, depth + 1);
	}
}

int dp(int node, int depth, int to_select) {
	if (depth == tree_height) {
		return tree[node];
	}
	if (calculated[node][to_select])
		return T[node][to_select];

	int best_sol = tree[node];
	for (int i = 1; i < to_select; i++) {
		int sub_sol = dp(node * 2 + 1, depth + 1, i) + dp(node * 2 + 2, depth + 1, to_select - i);
		if (sub_sol > best_sol)
			best_sol = sub_sol;
	}
	T[node][to_select] = best_sol;
	calculated[node][to_select] = true;
	return best_sol;
}

int main() {

	scanf("%d", &tree_height);
	while (tree_height != -1) {
		scanf("%d", &cut_limit);

		readInPreOrder(0, 0);

		memset(calculated, false, sizeof(calculated));
		oo = T[0][0];
		int sol = dp(0, 0, cut_limit);
		printf("%d\n", sol);

		scanf("%d", &tree_height);
	}

	return 0;
}