problem: https://codeforces.com/contest/1132/problem/C

TLE solution: https://codeforces.com/contest/1132/submission/124402631

n, q <= 5000

we can skip 2 painters, so just iterate through all pairs (i, j) ignore i and jtn painter, and maximize the answer.

time complexity: O(2 * n + q * q * 3)

space complexity: O(3 * n)

please help if you can find why I am getting TLE :)

thank you.

**update**

AC https://codeforces.com/contest/1132/submission/124404923

creating a vector in each iteration cause TLE :(

**how to avoid TLE**

- check time complexity will fit in the problem

- C++ — use FAST IO, use `'\n'`

instead of `endl`

, use `int`

(if needed)

- make sure your debug statement will not print anything on judge

- recursive dp sometime gives TLE, try iterative

- creating `vector`

, `vector.push_back()`

in nested loop is scary (check this comment for better understanding)

**if (nothing works)**

Time complexity is more like O(n*n*q):

For every i (n) take every j > i (/2) and connect q-2 segments () and check if its max.

You see that you have 3 levels of "for" in your code, right?

click hereAh, sorry, now I see what you did in third for-loop. Then question is — do you really need so many slow long longs?

I have changed

`long long int`

to`int`

still TLE (check the code again)`using ll = int;`

Going to help because it's a reasonably written blog.

You're correct about the solution and time complexity, that's not the issue. It's the implementation, and more specifically working heavily with vectors within the inner loop. Not all operations are created equal, so $$$O(q^2)$$$ of straightforward arithmetic will pass easily, but $$$O(q^2)$$$ of allocating new vectors is much, much heavier in practice.

I've done minimal changes to the code — in particular, I've made $$$b$$$ a fixed size and hence avoided allocating any memory within the loop. All the logic is the same but the speed increase is nearly 10x (at least locally for me). Here is your accepted code: AC. You can compare it to yours to see the exact changes.

Edit: I see you've figured it out yourself. Good job.yes Enchom got it. thank you very much.

But why

isn't this lines are the same allocations?This got AC too, with almost the same time as your's. Thought b is still a vector<vector< int> >. I just thrown out .push_back()'s and written above code of your's. What is the difference?

Whether it's statically allocated array, or a vector with fixed size, it doesn't matter. Both yours and mine are essentially the same

The important thing is that the lines you mentioned are not allocations, but simple assignments. There is no memory allocation/deallocation happening in the background since the vector does not change its size.