In the last Educational Codeforces Round 134, I did a submission for Problem B. In this submission, I got a TLE. While this submission got Accepted.
The only difference both of these codes are having, is of the "abs()" function. When I used "abs()" (Although, it was redundant) it gave TLE, no loops nothing. And when I just removed (effectively) "abs()" in it, it got Accepted.
I'm wondering if "abs()" alone can cause this TLE, or there is something, very subtle about it, which was causing it. Please refer to the Links given above for both of my submissions and, in case you want to see it, the problem.
*Edit 1 : Apart from whatever mentioned above, this submission also has a difference of "vector<vector> grd(n, vector(m, 0));" (which again is a redundant thing as per the logic of code)
This doesn't seem to be causing any TLE, or is it?
That is not the only difference, the TLE code also contains this line:
vector<vector<int>> grd(n, vector<int>(m, 0));. I removed it and got AC: 169902171.Oh yes, my bad. Still this doesn't seem to be causing TLE, or is it?
The line is causing TLE because it tries to create a matrix of size $$$nm$$$, i.e. $$$10^6$$$ ints. If you do that for every test case, then you do that $$$10^4$$$ times, i.e. $$$10^{10}$$$ ints allocated in total, that takes too much time. You might think that since it is not used, the compiler will optimize it out, but apparently not.