Hints: https://atcoder.jp/contests/arc197/editorial/12878

Problems that require maximizing some value are often called optimization problems. Unlike problems asking for the sum over all cases, in optimization problems it can be effective to restrict attention to special cases. This editorial takes that approach.

Let \(\mathrm{avg}(x)\) denote the average of a subsequence \(x\), and let \(\mathrm{score}(x)\) denote its score.

[1] Operations that never decrease the score

Our goal is to show that there exists an optimal subsequence with a simple structure. We do this by identifying two operations on subsequences that never decrease the score.

Operation 1

Let \(x\) be a subsequence, and let \(A_i\) satisfy:

• \(A_i \le \mathrm{avg}(x)\),
• \(A_i\) is not in \(x\).

If \(x'\) is obtained by adding \(A_i\) to \(x\), then \(\mathrm{score}(x)\leq \mathrm{score}(x')\).

Since \(\mathrm{avg}(x')\leq \mathrm{avg}(x)\), this is immediately proved. We call this addition Operation 1.

Operation 2

Let \(x\) be a subsequence, and let \(A_i,A_j\) satisfy:

• \(\mathrm{avg}(x) < A_i < A_j\),
• \(A_i\) is not in \(x\),
• \(A_j\) is in \(x\).

If \(x'\) is obtained by removing \(A_j\) and adding \(A_i\), then \(\mathrm{score}(x)\leq \mathrm{score}(x')\).

Again, since \(\mathrm{avg}(x')\leq \mathrm{avg}(x)\), this is immediately proved. We call this modification Operation 2.

[2] Computing the answer

Let \(x\) be an optimal subsequence, and apply Operations 1 and 2 as long as possible. Operation 1 increases the length of \(x\), while Operation 2 keeps the length fixed but strictly decreases the sum of its elements, so this process terminates after finitely many steps.

Since neither operation decreases the score, we conclude: there exists an optimal subsequence on which neither Operation 1 nor Operation 2 can be applied.

Hence, if we sort \(A\) in ascending order, there is an optimal subsequence of the form \(x=(A_1,\ldots,A_n)\). The scores for \(n=1,2,\ldots,N\) can be easily computed (for example, by binary search or two pointers). By implementing this method properly, the answer can be found in \(O(N\log N)\) time.

• Sample implementation: https://atcoder.jp/contests/arc197/submissions/65482041