USACO 2021 US Open Contest Silver Division - Acowdemia

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can sort the array and run a binary search on the answer. In order to check whether we can get to a certain target, we can rely on checking if we have enough resources to bring everything to the target, while also not having to add way too much to a single paper.

Source code

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

#include <bits/stdc++.h>
using namespace std;

int n, v[100002], v2[100002], k, L;

bool indexing(int target) {
    long long dif = 0;
    for (int i = n; i >= n - target + 1; i--) {
        dif += max(0, target - v[i]);
        if (target - v[i] > k) {
            return 0;
        }
    }
    if (dif > 1LL * k * L) {
        return 0;
    }
    return 1;
}
int main() {
    cin >> n >> k >> L;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    sort(v + 1, v + n + 1);

    int L = 0;
    int R = n;
    int ans = 0;

    while (L <= R) {
        int mid = (L + R) / 2;
        if (indexing(mid)) {
            ans = mid;
            L = mid + 1;
        } 
        else
            R = mid - 1;
    }

    cout << ans;
    return 0;
}