Editorial for Coconut Canopy

Approach

Each tree at position $n_i$ drops coconuts into the two neighboring positions $n_i - 1$ and $n_i + 1$. We can therefore compute, for every street position, how many coconuts would land there if we placed a basket on that slot. Now, we only need the to sum the values of the top $k$ locations. Sorting the values in descending order and summing the largest $k$ entries (or all of them if $k > n$) maximizes the overnight harvest.

Building the counts takes $O(n + m)$ and the sort dominates with $O(n \log n)$.

A linear-time solution is also possible.

Solution (Python)

n,m,k = map(int,input().split())
locs= list(map(int,input().split()))

cocs = [0 for i in range(n)]
for i in locs:
    loc = i-1
    if(0 <= loc-1 < len(cocs)):
        cocs[loc-1] += 1
    
    if(0 <= loc+1 < len(cocs)):
        cocs[loc+1] +=1

cocs.sort(reverse=True)

i = 0
ans = 0
while (i < k and i < len(cocs)):
    ans += cocs[i]
    i+= 1

print(ans)