So, I’m doing this problem and my code is over here. It’s complexity is O(\log H \cdot 2^N \cdot N), which seems to TLE. Is the binary search slowing it down too much, and if so, how should I fix it?
i think std::vector's constant factor is causing the TLE
So you’re saying if I switched from an std::vector to an array (resetting it after each run), it would work?
Also, is the complexity supposed to pass?
i take that back; i tried using arrays instead and it still TLE’d D:
The binary search is unnecessary with dynamic programming, unfortunately it looks like the time limit is designed to make the extra logn too slow.
Usually tiny constant factors like vector vs. array do not matter. Unless you are doing something unintended, like perhaps allocating 10million vectors.