Why does the code run faster if I swap the indices in a matrix?

Revision en2, by TheScrasse, 2020-03-21 09:56:02

Hi everyone, I have just tried to solve the problem 161D.
If I use a matrix dp[50010][510], I get a tle verdict, even if the time complexity of the solution is $O(nk)$, $nk < 10^8$ and the constant factors are quite small. But if I use a matrix dp[510][50010] and I swap the indices, I get ac with a time of 498 ms (much less than the time limit).
Why does it happen?
Thanks

Submission with tle verdict: 73781168
Submission with ac verdict: 73781989

#### History

Revisions

Rev. Lang. By When Δ Comment
en2 TheScrasse 2020-03-21 09:56:02 7 Typo fixed
en1 TheScrasse 2020-03-20 13:35:06 707 Initial revision (published)