For the recent contest (Codeforces Round #788 (Div. 2)), I was practicing submitting problem C after the contest. I got TLE on submitting the below code: https://mirror.codeforces.com/contest/1670/submission/156232289
However, after I changed the vectors to become global (as you can see in the submission below), the code got accepted: https://mirror.codeforces.com/contest/1670/submission/156232089
Can anyone explain why? I am guessing it is because of too much memory usage, but I am not sure and would appreciate any insights. Moreover, how can I know when to keep vectors global in the future?
Thank you!
in the first code in every test you are creating a vector of size $$$10^5$$$ and in the worst case you will make $$$O(N*t) = 10^{10}$$$ operations.
if you create the vectors of size $$$n$$$ (not $$$N$$$) it will not give TLE because the sum of the values of n is at most $$$10^5$$$.
modified code: 156234578
Ahh, that makes sense. Thanks!