USACO 2020 JAN #1 (Silver): Berry Picking

Bessie and her little sister Elsie are picking berries in Farmer John’s berry patch. Farmer John’s patch has exactly N berry trees (1≤N≤1000); tree i contains exactly Bi berries (1≤Bi≤1000). Bessie has exactly K baskets (1≤K≤1000, K even). Each basket can hold as many berries from a single tree as Bessie wants, but cannot contain berries from two different trees as their flavors will clash with each other. Baskets may remain empty.

Bessie wants to maximize the number of berries she collects. However, Farmer John wants Bessie to share with her little sister, and so Bessie will have to give Elsie the K/2 baskets with the largest number of berries. This means that Elsie may even end up with more berries than Bessie, which is very unfair, but unfortunately, sibling dynamics are not always fair.

Help Bessie figure out the maximum number of berries she can collect.

INPUT FORMAT (file berries.in):

The first line of input contains space-separated integers NN and KK.

The second line contains NN space-separated integers B1,B2,…,BN.B1,B2,…,BN.

OUTPUT FORMAT (file berries.out):

A single line with the answer.

SAMPLE INPUT:

5 4
3 6 8 4 2

SAMPLE OUTPUT:

8

If Bessie fills

• one basket with 6 berries from tree 2
• two baskets, each with 4 berries from tree 3
• one basket with 4 berries from tree 4

then she receives two baskets each with 4 berries, giving her 8 berries in total.

Problem credits: Nathan Pinsker

First when I saw this question, this question was so hard; How was I going to figure out how many berries can one get and when was I going to divide a tree into multiple baskets???

But eventually I figured out that you don’t have to; and also figured that this is a binary search question.

As you search through the numbers (and let’s call that number M), if more than N baskets can be filled with M berries, then it is possible that Bessie and Elsie each get M*N/2 Berries. Using this logic, we can see if there are more than N baskets of M, which we binary search, and if it doesn’t, it may still count (Bessie might still get more amount then before, since it would be a higher number of M.), therefore see how much Bessie would still get after she gives away N/2 baskets of M.

So, here’s my code:

//
//  main.cpp
//  Berry Picking Fix
//
//  Created by Shin Lee on 27/03/2020.
//  Copyright © 2020 Shin Lee. All rights reserved.
//

#include <bits/stdc++.h>
using namespace std;
int n, k; int berries[1005];int d;
bool cmp(int a, int b){return a%d>b%d;}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    int m =0;
    for(int i=0;i<n;i++){
        cin >> berries[i];
        m=max(m,berries[i]);
    }
    int ans = 0;
    for(int i=1;i<=m;i++){
        int cnt = 0;
        for(int j=0;j<n;j++){
            cnt+=berries[j]/i;
        }
        if(cnt<k/2)break;
        if(cnt>=k){
            ans = max(ans,i*(k/2));
            continue;
        }
        d = i;
        sort(berries,berries+n,cmp);
        int sum = i*(cnt-k/2);
        for(int j=0;j<n and j+cnt!=k;j++){
            sum+=berries[j]%d;
        }
        ans = max(ans,sum);
        
    }
    cout << ans;
    
    return 0;
}