Hi codeforces community!

So I was solving this problem: 1703G - Хороший ключ, плохой ключ

I wrote first solution: 283940469 ~ TLE

I wrote second solution: 283940935 ~ AC

Two programs are very similar to each other so i will list most notable differences between them:

• First solution uses C-array a of size N = 1e5 defined globally. Second solution uses vector of size n which is defined for each test case
• First solution uses vector<vector<ll>> dp, with N rows and each row is of size 31 and for each test it fills every row with vector<ll>(31, -1). Second solution uses similar dp vector but has n rows and is defined in the solve function
• First solution accesses variables n, k, dp from the global scope. Second solution passes references to vectors as parameters and variable k also as parameters for each recursive call.

I sincerely thought first solution would be faster than second solution.

So, my question is why is that first solution gets TLE but second solution gets AC?