ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1167. Bicolored Horses

memory limit
Posted by ahmed ezz 27 Feb 2023 02:01
so in my solution i use o(N^3) space and i got mle ( i expected that) but what makes me confused that people says they passed wih o(n^3) time i know there is a different between memory and time complexity but i have some doubts they may also used o(n^3) space too
so can someone tell me whether they added a new cases or whats is the problem?
Re: memory limit
Posted by Finn Pomfret 3 Sep 2024 21:51
I assume that you are using an array dp[N][N][k] and that the first dimension of this array is the index that you are currently at, you don't actually need this dimension because the index which you are currently at only relies on the previous index's states, this means that you can reduce the first dimension from size N to size 2