Help needed in solving problem ZCO14003

I tried my level best but I am not able to answer the problem without getting a TLE. Please tell the code which give the correct answer as I have tried many times but unable to answer the problem fully. It always shows partially correct.

Are you sorting the input? If yes, how are you doing it?

No I am not sorting input. But I am using nested for loops to count the number of elements greater than or equal to the current element and then multiplying it to the budget. Then I find the max revenue using 2 variables.

@anshmishra471 If both the outer loop and the nested loop run n times each, your code will do roughly n^2 operations. The maximum value of n in this problem is 5 \times 10^5, which would make n^2 equal to 25 \times 10^{10}. The time limit for this problem is 1 second. The maximum number of operations that can be done in a second is approximately 10^8 to 10^9, but your code is doing around 25 \times 10^{10} operations, which will certainly time out.

A better way to solve this problem is to sort the input, and then for each index i in the array, the number of elements greater than or equal to the element at i^{th} index will simply be the number of elements to the right of i, which is n - i - 1, plus 1 to count the i^{th} element also. I have assumed 0-based indexing.

Before solving more problems, consider reading about asymptotic complexity if you haven’t done that already.

Thanks a lot for help :slight_smile: