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