PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
View solution here.
In the solution, it says the complexity of the solution is O( m * n * log(t) ). For arguments sake, lets assume log(t) is negligible. So complexity is O ( m * n ). But there are 20 test cases. So overall, it becomes, 20 * m * n = 20 * 10000 * 10000 = 2*10^9. That’s approximately 20 seconds. Time limit given is 1 seconds. So the solution will definitely time out.
For a given t, we don’t really need O(m * n) dp to calculate maximum nuts the squirrels can get. For each tree, we simply calculate the number of nuts that will drop in time t. After that, we sort those numbers, and pick the first n highest numbers. So complexity becomes O( m + m*log(m) + n ). I saw everyone using this one in their code.