Problem 4: Architecture

https://open.kattis.com/problems/architecture

Let $x$ be the maximum of $x_1,...,x_R$(the second line of input), and let $y$be the maximum of $y_1,...,y_C$ (the third line of input).

If $x = y$, we can always assign building heights. For example, consider the input:

4 4
3 2 4 2
1 4 1 1

Here, $x=y=4$. Then, we can always use the row and column of $x$ and $y$ for the skylines, and fill the rest of the table with 0s:

$\begin{pmatrix} 0 & 3 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 1 & 4 & 1 & 1 \\ 0 & 2 & 0 & 0 \end{pmatrix}$

If $x > y$, there must still be an entry in the table with value $x$, so that the eastern skyline can have $x$ in one row. Then, the column with that entry will have to have a skyline of height $\geq x$ too, but as the maximum northern skyline height $y$ is less than$x$, this is impossible. Similarly, $x<y$is also impossible.

So, output possible if $x=y$, and output impossible otherwise.

C++ has a function max_element() which finds the max number in a vector. Example usage:

vector<int> v = {3, 1, 4, 7, 2};
int m = *max_element(v.begin(), v.end()); // m will be 7