The common approach to maximization of average or median is to boil it down to the predicate of “does the answer exceed \(K\)?” and find the answer by binary search.

Does the average exceed \(K\)?

“The average of \(x_1, \dots, x_n\) is greater than \(K\) \(\Leftrightarrow\) \((x_1 - K) + \dots + (x_n - K)\) is more than \(0\),” so, defining \(B_i = A_i - K\), it is sufficient to check if the maximum sum of \(B_i\) corresponding to the chosen cards is greater than \(0\).

Does the median exceed \(K\)?

“The median of \(x_1, \dots, x_n\) is greater than \(K\) \(\Leftrightarrow\) the number of elements greater than \(K\) in \(x_i\) is greater than the number of elements less than or equal to \(K\),” so, defining \(B_i = 1\) if \(A_i \ge K\) or otherwise \(B_i = -1\), it is sufficient to check if the maximum sum of \(B_I\) corresponding to the chosen cards is positive.

Maximization of sum of \(B_i\)

In order to evaluate the above-mentioned predicates, we need to find the maximum sum of \(B_I\) corresponding to the chosen cards. This can be computed with the following Dynamic Programming (DP).

• \(f_k :=\) the maximum sum of \(B_i\) when the cards are chosen from the first \(k\) elements so that the \(k\)-th card is chosen
• \(g_k :=\) the maximum sum of \(B_i\) when the cards are chosen from the first \(k\) elements so that the \(k\)-th card is not chosen

Let \(f_0 \leftarrow 0, g_0 \leftarrow 0\), and compute \(f_k \leftarrow \max(f_{k - 1}, g_{k - 1}) + B_k, g_k \leftarrow f_{k - 1}\) in the increasing order of \(k\). Thus the predicate can be evaluated in an \(O(N)\) time.

Handling precision errors

The average is not necessarily an integer, so it is difficult to find the precise value. In this problem, the output is considered to be a correct solution if the relative or absolute error from the true value is at most \(10^{-3}\), so we ca use the following ways.

• Multiply each \(A_i\) by \(10^3\) and find the maximum integer such that the average may exceed \(K\). Output \(10^{-3} K\). Sample code (C++)
• Let \(l\) be the lower bound, and \(h\) be the upper bound, of the binary search. Continue binary search while \(\frac{h - l}{h} > 10^{-3}\). After the search ends, output \(l\). Sample code (C++)
  • Note 1. In this problem, the average is always at least \(1\), so we can assume that \(l \geq 1\). Therefore, the relative error is always less than the absolute error.
  • Note 2. Generally, in binary search we let \(m = \frac{l + h}{2}\) and evaluate the predicate for \(K = m\). However, as in this problem, if the answer is always greater than or equal to \(1\), and the objective is to reduce the relative error below a threshold, then using \(m = \frac{l + h}{2}\) requires less worst iterations. This can be understood by considering minimizing \(\max(\frac{x - l}{x}, \frac{h - x}{h})\).