# Problem Info

Type: **Regional**

Continent: **South America**

Year: **2008**

Link: **4212 - Candy**

# Problem Statement

In this contest a random number of boxes containing candies are disposed in M rows with N columns each (so, there are a total of $M x N$ boxes). Each box has a number indicating how many candies it contains.

The contestant can pick a box (any one) and get all the candies it contains. But there is a catch (there is always a catch): when choosing a box, all the boxes from the rows immediately above and immediately below are emptied, as well as the box to the left and the box to the right of the chosen box. The contestant continues to pick a box until there are no candies left.

Can you maximize the number of candies he can pick?

# Explanation

There's a presentation I've written to teach how to solve the problem. It is in Spanish, I don't have enough time now to write the explanation here but I will as soon as I can.

The presentation: 4212-Candy.pdf

# Code

The C++ code that solves the problem using Top-Down approach with memoization is the following(4212-memo.cpp):

#include <iostream> #include <algorithm> #include <stdint.h> #include <map> using namespace std; uint32_t row[100002]; uint32_t max_rows[100002]; uint64_t f(uint32_t* array, uint32_t index, uint32_t size, map<uint32_t, uint64_t>& memo) { if (index == size - 1) return array[index]; if (index == size - 2) return max(array[index], array[index + 1]); if (memo.find(index) != memo.end()) return memo[index]; uint64_t tmp = array[index] + f(array, index + 2, size, memo); tmp = max(tmp, f(array, index + 1, size, memo)); memo[index] = tmp; return tmp; } int main() { uint32_t n, m; cin >> m >> n; map<uint32_t, uint64_t> memo; while (m > 0) { for (uint32_t i(0); i < m; ++i) { for (uint32_t j(0); j < n; ++j) { cin >> row[j]; } memo.clear(); max_rows[i] = f(row, 0, n, memo); } memo.clear(); cout << f(max_rows, 0, m, memo) << '\n'; cin >> m >> n; } }

The C++ code for the Bottom-Up approach is the following(4212.cpp):

#include <iostream> #include <algorithm> #include <stdint.h> using namespace std; uint32_t row[100002]; uint32_t max_rows[100002]; uint32_t dp(uint32_t* r, uint32_t size) { if (size > 1) { r[1] = max(r[0], r[1]); } for (uint32_t i(2); i < size; ++i) { r[i] = max(r[i-1], r[i] + r[i-2]); } return r[size-1]; } int main() { uint32_t n, m; cin >> m >> n; while (m > 0) { for (uint32_t i(0); i < m; ++i) { for (uint32_t j(0); j < n; ++j) { cin >> row[j]; } max_rows[i] = dp(row, n); } cout << dp(max_rows, m) << '\n'; cin >> m >> n; } }