(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';
}