Colored Balls
Contest: Educational Codeforces Round 164 (Rated for Div. 2)
Difficulty rating: 1800
Tags: combinatorics, dp, math, sortings

There are balls of $$$n$$$ different colors; the number of balls of the $$$i$$$-th color is $$$a_i$$$.

The balls can be combined into groups. Each group should contain at most $$$2$$$ balls, and no more than $$$1$$$ ball of each color.

Consider all $$$2^n$$$ sets of colors. For a set of colors, let's denote its value as the minimum number of groups the balls of those colors can be distributed into. For example, if there are three colors with $$$3$$$, $$$1$$$ and $$$7$$$ balls respectively, they can be combined into $$$7$$$ groups (and not less than $$$7$$$), so the value of that set of colors is $$$7$$$.

Your task is to calculate the sum of values over all $$$2^n$$$ possible sets of colors. Since the answer may be too large, print it modulo $$$998\,244\,353$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the number of colors.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 5000$$$) — the number of balls of the $$$i$$$-th color.

Additional constraint on input: the total number of balls doesn't exceed $$$5000$$$.

Output format:
Print a single integer — the sum of values of all $$$2^n$$$ sets of colors, taken modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Note:
Consider the first example. There are $$$8$$$ sets of colors:

- for the empty set, its value is $$$0$$$;
- for the set $$$\{1\}$$$, its value is $$$1$$$;
- for the set $$$\{2\}$$$, its value is $$$1$$$;
- for the set $$$\{3\}$$$, its value is $$$2$$$;
- for the set $$$\{1,2\}$$$, its value is $$$1$$$;
- for the set $$$\{1,3\}$$$, its value is $$$2$$$;
- for the set $$$\{2,3\}$$$, its value is $$$2$$$;
- for the set $$$\{1,2,3\}$$$, its value is $$$2$$$.

So, the sum of values over all $$$2^n$$$ sets of colors is $$$11$$$.

Example input:
3
1 1 2

Example output:
11

Example input:
1
5

Example output:
5

Editorial:
For a fixed set of colors, this is a standard problem with the following solution: let's denote the total number of balls as $$$s$$$, then the value of the set is $$$\left\lceil\frac{s}{2}\right\rceil$$$; but there is an exception in the case when there is a color with more than $$$\frac{s}{2}$$$ balls, then the value is the number of balls of this color.
So the answer depends only on whether there is a color that has more balls than all the others combined.
Using the aforementioned fact, we can come up with the following solution: let's iterate over the total number of balls in the set (denote it as $$$j$$$) and increase the answer by $$$\left\lceil\frac{j}{2}\right\rceil$$$ for each subset of colors with exactly $$$j$$$ balls in it. The number of subsets with the fixed number of balls can be calculated using simple knapsack dynamic programming.
It remains to consider the subsets of colors with a "dominant" color, because we added the wrong value to the answer for them. Let the "dominant" color be $$$i$$$ and the total number of balls in all other colors be $$$j$$$ ($$$j < a_i$$$). The answer should be increased by $$$a_i - \left\lceil\frac{a_i + j}{2}\right\rceil$$$ (the correct value of this set is $$$a_i$$$, but we have already added the wrong value in the answer — $$$\left\lceil\frac{a_i + j}{2}\right\rceil$$$, so we should compensate it) for each subset of colors with exactly $$$j$$$ balls in it (we can use the same dp as in previous case). Note that if you consider only $$$j < a_i$$$, you don't have to deal with the possibility that the "dominant" color could already be included in the subset.
This solution works in $$$O(nS)$$$ time, where $$$S$$$ is the total number of balls.