Acowdemia Silver WA (2021 US Open)

Problems and Contests
#1

Link to Problem

Here was my code during the actual contest. I haven’t bothered upsolving this contest yet, but I still want to know why I got WA on 7 test cases and MLE/RTE on 1 test case. Could someone direct me to the correct logic for this problem. My logic was to binary search on the answer for the maximum h-index. In the “works” function, I checked whether I could add a sufficient amount of articles to validate the h-index.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define dbg(x) for(auto& a: x) cout << a << " "

ll n, k, l;

bool works(vector<ll> arr, ll hIndex){
    ll addArticles = hIndex;
    for(int i=0; i<n; i++){
        if(arr[i] >= hIndex){
            --addArticles;
        }
    }
    if(addArticles > k) return false;
    vector<ll> cur;
    for(int i=0; i<n; i++){
        if(arr[i] < hIndex){
            cur.push_back(hIndex - arr[i]);
        }
    }
    sort(cur.begin(), cur.end());
    ll added = 0;
    for(int i=0; i<addArticles; i++){
        added += cur[i];
    }
    return (added <= k*l);
}

int main(){
    cin >> n >> k >> l;
    vector<ll> arr(n);
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());
    ll l = 0, r = 1000000000, ans = 0;
    while(l <= r){
        ll m = l + (r-l) / 2;
        if(works(arr, m)){
            ans = m;
            l = m+1;
        } else {
            r = m-1;
        }
    }
    cout << ans << endl;
}
#2

What’s the purpose of this line here?

#3

In case there are more articles than u can cite with the given h-index.

#4

Each article can only cite distinct papers. You aren’t handling that failure mode.

#5

Omg tysm.