Problem
https://codeforces.com/contest/1132/problem/C
TLE solution
https://codeforces.com/contest/1132/submission/124402631
Approach
n, q <= 5000
We can skip 2 painters, so just iterate through all pairs (i, j) ignore i and jth painter, and maximize the answer.
Time complexity: O(2 * n + q * q * 3)
Space complexity: O(3 * n)
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?
Ah, 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 inttointstill 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
b[0] = {l1, l2 - 1, 1}; b[1] = {l2, min(r1, r2), 2}; b[2] = {min(r1, r2) + 1, max(r1, r2), 1};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.