ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1167. Bicolored Horses

memory limit
Послано ahmed ezz 27 фев 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
Послано Finn Pomfret 3 сен 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