USACO 2020 January Contest Silver Division - Berry Picking

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The main idea is to set the maximum berries we can have per bucket, we loop through 1 - max(B) to simulate the possible combinations we can have. We use a frequency array to keep track of the max berries we can make for a certain berry. There are other solutions which can be used to solve the problem as well.

Source code

The source code in C++ can be seen below.

#include <fstream>
#include <map>
using namespace std;
ifstream cin("berries.in");
ofstream cout("berries.out");
int n, k, ans = 0, v[1001];
int check(int x) {
    int f[1001];
    for (int i = 0; i <= 1000; i++) {
        f[i] = 0;
    }
    int total = 0;
    for (int i = 1; i <= n; i++) {
        f[x] += v[i] / x;
        if (v[i] % x != 0) {
            f[v[i] % x]++;
        }
    }
    int curr = 0, sum = 0;
    for (int i = 1000; i >= 1; i--) {
        if (f[i] + curr <= k) {
            sum += i * f[i];
            curr += f[i];
            f[i] = 0;
        } else {
            sum += i * (k - curr);
            f[i] -= (k - curr);
            break;
        }
    }
    curr = 0, sum = 0;
    for (int i = 1000; i >= 1; i--) {
        if (f[i] + curr <= k) {
            sum += i * f[i];
            curr += f[i];
            f[i] = 0;
        } else {
            sum += i * (k - curr);
            f[i] -= (k - curr);
            break;
        }
    }
    ans = max(ans, sum);
    return sum;
}
int main() {
    int maxx = 0;
    cin >> n >> k;
    k /= 2;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        maxx = max(maxx, v[i]);
    }
    for (int i = 1; i <= maxx; i++) {
        check(i);
    }
    cout << ans;
    return 0;
}