Load Unbalancing

Observation 1: Make the Winning Item Last

Take any optimal order. Let $x$ be the item whose addition creates the final maximum value $F$. Right before adding $x$, its pile has load $L$. Since the rule always adds to a minimum pile, every pile has load at least $L$, and

$$F=L+x.$$

Now move every item after $x$ to before $x$, and put $x$ at the very end. After the old prefix, the minimum load is already $L$; adding more positive items cannot make the minimum load go down. So before adding $x$ last, the minimum load is at least $L$, and adding $x$ still achieves at least $L+x$.

So we only need to consider solutions where the item that creates the answer is the last item. Good, the permutation monster just lost most of its teeth.

For a fixed last item $x$, the best value is

$$x + H(A\setminus\{x\}),$$

where $H(S)$ is the maximum possible minimum pile load after arranging all items of $S$.

Observation 2: Greedy Minimum Load = Best Bottleneck Partition

Claim:

$$H(S)=\max_{S=B_1\cup B_2\cup\cdots\cup B_k}\ \min_{1\le r\le k}\sum_{i\in B_r} a_i.$$

One direction is obvious: any greedy run assigns items to piles, so it gives some partition. Its minimum load cannot beat the best partition bottleneck.

For the other direction, suppose we have a partition where every group has sum at least $L$. We can realize minimum load at least $L$ by greedy:

• while some group has current load $<L$, choose a group with minimum current load and output one of its remaining items;
• that group really has a remaining item, because its total assigned sum is at least $L$;
• greedy will put the item into that group, because it is currently a minimum pile.

Eventually all piles reach at least $L$. Any leftover items can be placed afterward; the minimum never decreases. So the greedy problem and the partition bottleneck problem are exactly the same here.

Observation 3: The Last Item Should Be Maximum

Let $x\le y$, and let $R$ be all other items. Compare making $x$ last versus making $y$ last:

$$\text{score}(x)=x+H(R\cup\{y\}),$$ $$\text{score}(y)=y+H(R\cup\{x\}).$$

Let $H(R\cup\{y\})=L$. Take an optimal partition for $R\cup\{y\}$ and replace $y$ by $x$ in its group. Only that group decreases, and it decreases by exactly $y-x$, so

$$H(R\cup\{x\})\ge L-(y-x).$$

Therefore

$$y+H(R\cup\{x\})\ge y+L-(y-x)=x+L=x+H(R\cup\{y\}).$$

So a larger last item is never worse. Remove one maximum element $mx$, solve the bottleneck partition problem on the remaining $m=n-1$ items, and add $mx$.

Checking a Candidate Bottleneck

For a fixed value $L$, we need to know whether the remaining items can form at least $k$ disjoint groups, each with sum at least $L$.

Use bitmask DP over the remaining items. For each mask, store the best pair

$$dp[mask]=(c,r),$$

where:

• $c$ is the maximum number of completed groups with sum $\ge L$;
• $r$ is the current unfinished group sum, with $0\le r<L$;
• pairs are compared lexicographically: larger $c$ is better, and for equal $c$, larger $r$ is better.

Transition by adding an unused item $a_i$:

$$(c,r)\to \begin{cases} (c+1,0), & r+a_i\ge L,\\ (c,r+a_i), & r+a_i<L. \end{cases}$$

Closing a group immediately when it reaches $L$ is optimal for this DP: once a group is already good enough, dumping more items into it is usually just wasting ammunition.

If we can reach $c\ge k$, then $L$ is feasible. Binary search the largest feasible $L$.

Complexity

There are only $m=n-1\le 17$ items after removing the maximum. One feasibility check costs

$$O(m2^m),$$

and binary search adds a factor of $O(\log \sum a_i)$. Memory is

$$O(2^m).$$

Given $\sum 2^n\le 2^{18}$, this easily fits. The low time limit is annoying, not fatal. Classic Codeforces nonsense.