Acowdemia

Algorithm

Binary search on the h-index. For each candidate h, try to add citations to the top h papers. If we have to add more than k citations to a paper, then the h-index is unattainable. If we have to add more than kl citations in total, then the h-index is also unattainable.

Python

def find(h,papers,k,l):
    total_citations = k*l
    papers.sort(reverse=True)
    s = 0
    for i in range(len(papers)):
        if papers[i] <= h:
            s = i
            break
    #print(papers,s)
    for i in range(h-s):
        diff = h-papers[i+s]
        if diff > k:
            return False
        total_citations -= diff
        if total_citations < 0:
            return False
    return True

# binary search
n,k,l = map(int,input().split())
papers = list(map(int,input().split()))

low = min(papers)
high = max(papers)+k
mid = 0

while low <= high:
    mid = (high + low) // 2
    x = find(mid,papers,k,l)
    if x:
        low = mid + 1
    else:
        high = mid - 1
print(min(low,high))