(Analysis by Dhruv Rohatgi, Benjamin Qi)

Small $K$:

After sorting the trees in decreasing order of $B_i$, we don't need to consider trees outside of the first $K.$ Furthermore, if we decide to select $b>0$ baskets from tree $i,$ then each basket should have either $\left\lfloor \frac{B_i}{b}\right\rfloor$ or $\left\lfloor \frac{B_i}{b}\right\rfloor+1$ berries. Using these observations, we can do some sort of backtracking.

Full Solution:

Let $b$ the minimum number of berries in one of the buckets that Elsie receives. Without loss of generality, we can assume that all of Elsie's buckets contain exactly $b$ berries. Now our goal is to maximize the number of berries placed into $K$ buckets of size at most $b$ such that at least $\frac{K}{2}$ buckets have exactly $b$ berries inside.

Consider a single tree's allotment into the buckets in an optimal solution. There's no point having multiple buckets with less than $b$ berries from this tree. So all buckets will have exactly $b$ berries aside from at most one.

Thus, it's clearly optimal to repeatedly fill buckets of size exactly $b$ until we run out of buckets or all trees have less than $b$ berries remaining. If we still have buckets to fill, sort the remaining trees by $B_i\pmod{b}$ and iterate from the largest to the smallest value.

We can repeat this procedure for each $b=0\ldots \max(B_i),$ which runs in $O(\max(B_i)\cdot N\log N)$ time.

Dhruv Rohatgi's code:

#include <iostream>
#include <algorithm>
using namespace std;
 
int N,K;
int A[100000];
int mod;
 
bool cmp(int a,int b)
{
	return (a%mod) > (b%mod);
}
 
int main()
{
	freopen("berries.in","r",stdin);
	freopen("berries.out","w",stdout);
	cin >> N >> K;
	int M = 0;
	for(int i=0;i<N;i++)
	{
		cin >> A[i];
		M = max(M, A[i]);
	}
	int best = 0;
	for(int b=1;b <= M;b++)
	{
		int full = 0;
		for(int i=0;i<N;i++)
			full += A[i]/b;
		if(full < K/2)
			break;
		if(full >= K)
		{
			best = max(best, b*(K/2));
			continue;
		}
		mod = b;
		sort(A, A+N, cmp);
		int cur = b*(full - K/2);
		for(int i=0;i<N && i+full<K;i++)
			cur += A[i]%b;
		best = max(best,cur);
	}
	cout << best << '\n';
}