Submission is All You Need

The first thing to notice is that sum gives us a boring but very strong baseline: if we never use mex, the score is

$\sum S_i.$

So the whole problem is really: when does a mex operation beat just summing those same elements?

Suppose we choose some subset $T$ and use mex on it. Compared to using sum on the same elements, the extra profit is

$\text{mex}(T) - \text{sum}(T).$

We only care about subsets where this is positive. Otherwise, just sum the elements and move on with life.

What can a useful mex subset look like?

Let $\text{mex}(T)=k$. Then $T$ must contain every number

$0,1,2,\dots,k-1,$

and it must not contain $k$.

Any element greater than $k$ does not help increase the mex. It only increases $\text{sum}(T)$, which makes the mex operation worse compared to summing. So an optimal useful mex subset never needs random big numbers stuffed inside. That would be self-sabotage, which is usually bad outside of Codeforces too.

The cheapest subset with mex $k$ is exactly one copy of each of

$0,1,2,\dots,k-1.$

Its sum is

$0+1+2+\cdots+(k-1)=\frac{k(k-1)}{2}.$

So the best possible gain for mex $k$ is

$k - \frac{k(k-1)}{2}.$

Now check small values:

• $k=1$: subset $\{0\}$, gain $1-0=1$.
• $k=2$: subset $\{0,1\}$, gain $2-1=1$.
• $k=3$: subset $\{0,1,2\}$, gain $3-3=0$.
• $k\ge 4$: the sum grows too fast, so the gain is negative.

So mex can only improve the answer by $1$, and every improving mex operation needs exactly one zero.

That gives a clean upper bound: if there are $c_0$ zeroes, the answer is at most

$\sum S_i + c_0.$

Can we always achieve that? Yep. For every zero, take the subset $\{0\}$ and use mex, gaining $1$ instead of the zero's normal sum contribution of $0$. Then sum all remaining elements normally.

So the maximum score is simply:

$\boxed{\sum S_i + \#\{i : S_i=0\}}.$

That's it. Count zeroes, add them to the sum. Very 800-rated, very "wait, that's the whole problem?"