Table with Numbers

The table itself is bait. We do not care which exact cells get incremented, and duplicates are totally fine: if we make the pair $(1,1)$ twice, the sum increases by $2$. So the whole problem is just: how many valid pairs can we form?

A pair is valid if one number can be used as the row and the other can be used as the column. So we care about three counts:

• $R = \#\{a_i \le h\}$: numbers that can be row indices.
• $C = \#\{a_i \le l\}$: numbers that can be column indices.
• $U = \#\{a_i \le \max(h,l)\}$: numbers that can be useful at all.

Now get the obvious upper bounds out of the way:

• Each successful pair needs one row-capable number, so the answer is at most $R$.
• Each successful pair needs one column-capable number, so the answer is at most $C$.
• Any $a_i > \max(h,l)$ cannot be used in a successful pair at all. Since each successful pair consumes two useful numbers, the answer is at most $\left\lfloor U/2 \right\rfloor$.

Therefore,

$$\text{answer} \le \min\left(R, C, \left\lfloor \frac U2 \right\rfloor\right).$$

The only real question is whether this bound is always achievable. It is.

Assume first that $h \le l$. Then every row-capable number is also column-capable, because $a_i \le h$ implies $a_i \le l$. The useful numbers are exactly the column-capable numbers, so $U=C$.

Let

$$M = \min\left(R, \left\lfloor \frac C2 \right\rfloor\right).$$

Choose any $M$ row-capable numbers to be the row side of the pairs. Since $M \le \left\lfloor C/2 \right\rfloor$, after removing those $M$ numbers, there are still at least $M$ other column-capable numbers left. Pair them arbitrarily with the chosen row numbers. Every pair is valid.

If $h > l$, the same argument works with rows and columns swapped. So the upper bound is tight, and the formula is the answer.

The common wrong assumption is thinking about distinct cells. Nope. The same cell can be hit multiple times, and each hit still adds $1$. Another easy trap is counting row-capable and column-capable values separately without remembering that one array element cannot play both roles in the same pair. That is exactly why the $\left\lfloor U/2 \right\rfloor$ bound exists.

For each test case, just count values $\le h$, values $\le l$, and values $\le \max(h,l)$.

Complexity: $O(n)$ per test case, with $O(1)$ extra memory.