• + 0 comments

    If you're computing the array each time it seems this solution would be on the O(T*n*m) ~ 10^9 which would explain why you ran out of time.

    Alternatives:

    Option 1)
    Precompute the array once for n = 1000. Read the results for each test case out of the array.

    Option 2)
    Use a recursive function with memoization (easy for this problem)