This solution is actually quite close to the timeout limit and will sometimes not even make it. Not that mine is any better really!

It's like a waterfall!

Very impressive

I agree that this feels much harder than 6kyu, very fun, but requires quite a bit of trickery both performance and golf wise

I have now realised that I'm doing a lot of redundant work, I had originally intended to implement memoisation in the helper functions, but now see that I should just have advanced the index of my output vector in a loop. At least the calculations of the elements should be quite efficient.

I think this is a really interesting puzzle that I'd love to give a go in R, I think I'm close to a solution but struggling to convert my code into efficient Python. Any chance for an R solution to be allowed directly? :)