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.