Problem
https://codeforces.me/contest/1132/problem/C
TLE solution
https://codeforces.me/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.me/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)