Блог пользователя Gaurav3478

Автор Gaurav3478, история, 3 года назад, По-английски

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://codeforces.me/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://codeforces.me/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!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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