You could ask at kata solving chat for some advice, because posting here might be considered a spoiler.
To solve this kata, I was able to use an approach very similar to other, much simpler 2 kyu (terribly overranked tho) task. Many people went some (IMO) harder way.

These 3 seconds might be time needed for compilation and startup, but once it's done, efficient solution should not take too long to pass all test cases.
Unfortunately I have not solved it in C++ so I'd have to create solution from scratch to verify it, but as far as I see it was solved in C++ quite recently, so I would rather expect the problem to be in your solution.
You can print something to console on every invocation of your function (remember to flush), so you would know how far it gets before timing out.