I recently attempted to solve TWOPATHS from the 2018 INOI. The common solution involves creating a 3 dimensional dp array, which means the expected complexity is O(nmk). I wrote a solution with this exact complexity and it passed most test cases, getting 48/100 points.
However, it TLEd on 4 inputs for some reason. Tried several variations of the code but it is TLEing in the same 4 cases. I find this very confusing since other solutions that passed look very similar to mine.
The way I solve it is by minimizing the sum of the left and right paths individually (ldp and rdp) and then going over all possible starting positions to find the maximum sum in the middle.
It would be amazing if anyone could help me figure out why my submission TLEs despite having no dynamic data structures or loops.
UPDATE: After testing a few things I believe this is happening because of the way cache works on CodeChef. This makes the order in which multidimensional arrays are iterated over matter a lot for code speed (upto 1.5 seconds of difference). Just compare this and this (the part that says “extra addition”).