dhiraj-01's blog

By dhiraj-01, 3 years ago, In English

Problem
https://codeforces.net/contest/1132/problem/C

TLE solution
https://codeforces.net/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.net/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)

Full text and comments »

  • Vote: I like it
  • +31
  • Vote: I do not like it