Hi codeforces community!

So I was solving this problem: 1703G - Good Key, Bad Key

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?

In first solution you are refilling the whole $$$dp$$$ array

So for each test case it does at least N operations (which will lead to TLE when you have 10^4 testcases)

You reset your

`dp`

vector in each test case. In the first submission your`dp`

size is $$$N$$$ so you'll get $$$O(TN)$$$ complexity, which reaches $$$10^9$$$.