I have these two codes for the recent Codeforces Educational round 99.
Both of these have a really small difference, yet one gives AC, and the other gives TLE.
I have used vectors, which allocate memory dynamically, (even though it is a function call), but I think reducing the allocations by just 24 is too less to make any difference at all, that too I am allocating a vector of size only 4.
In the case of AC, exec time = 1.5 seconds, where as int TLE case, exec time > 2 seconds.
In the AC case, the func function is called log2(109) = 30 times, and each time one dynamic allocation is done of size = 8 (2 vectors of size 4), total = 240.
Whereas in the TLE case, the func function is called log2(109) = 30 times, and each time 24 dynamic allocations are done of size = 8 (2 vectors of size 4), total = 5760.
Why is such a small difference in allocation making such a huge difference. These differ only by a factor of 24 in memory allocation. Considering the array size of only 8 * 8 bytes, and the memory allocation is very fast, why does this make a huge difference.
I was expecting both to have similar running time, but the reality was quite different, can someone tell me the reason.