← All solutions

Shortest judge solution: 818 bytes. Shortest team solution (during contest): 1178 bytes.

Python solutions by the judges: both Pypy and CPython

If not for the top-down view, this problem would be really straightforward. Since solving easy problems is easier than solving harder problems, let’s go over that first.

Consider the highest stack of crates in the input, and assume it has height H₁. It has to appear both in the front view and the side view at least once. Assume that it appears m₁ times in the front view, and n₁ times in the side view, and without loss of generality, assume n₁ ≤ m₁. In that case, we will need at least m₁ stacks of height H₁, and we can achieve the correct side and front view by arranging m₁ stacks so that there is at least one in each of the m₁ columns and n₁ rows.

Then, proceed to the next height, H₂. Again, we have m₂ columns and n₂ rows that have to contain a stack with height H₂. The one thing that is different here is that it is possible for, say, m₂ to be zero – in which case we will put the stacks of height H₂ in the column(s) already containing stacks of height H₁. Following this pattern, we will use up a total of

∑ H_i · max(m_i, n_i)

crates. After placing all the crates for all the heights, the side and front views are already correct, so (disregarding the existence of the top view) we can just leave the remaining spaces empty.

Now, the existence of the top view changes two things in that strategy. First, at the end, we might have to leave a single crate (instead of zero crates) in some of the remaining spaces, to prevent the top view from noticing the spaces are empty. This is easy – we just keep track of how many spaces we filled, and then add to the final answer the number of spaces seen in the top view minus the number of spaces already filled.

The more tricky part is that due to the top view seeing empty spaces in some spots, it might be impossible to put a stack of height H_i in each of the m_i columns and n₁ rows using just max(m_i, n_i) stacks. We want to have as many stacks as possible to cover both a row and a column, and then we can make the remaining columns and rows covered by just putting a stack of height H_i wherever it was in the original input. Notice that this is a bipartite matching problem – we have a set of rows and a set of columns, and we can connect a row to a column when the top view shows a non-empty stack. So, for each height H_i appearing in the input, we run bipartite matching to find out how many stacks can cover both a row and a column, and then replace max(m_i, n_i) with m_i + n_i − Bipartite(i). Note that this formula works fine even if one of the sides is zero. Since the runtime of bipartite matching is super-linear, the worst-case for this problem is if all the columns and rows in the front and side views are of the same height. With r, c ≤ 100, this will easily run in time.