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

Обсуждение задачи 1146. Maximum Sum

How my O(n^4) solution got AC.
Послано Raman Gupta 17 дек 2012 00:44
I was little discouraged when my O(n^4) solution got AC.What remains the purpose of Dp ,if I could do it by complete search.

Please mail me the O(n^3),O(n^2),O(n) solution for this task,any or all complexity written here.
My mail id is royalbird.raman@gmail.com
thanks for your support
Re: How my O(n^4) solution got AC.
Послано Andrew Sboev [USU] 17 дек 2012 22:41
O(n) cannot be achieved in this problem, because of O(n^2) input.
Re: How my O(n^4) solution got AC.
Послано Lord_F 26 дек 2012 21:31
I think you use a kind of DP when you sum the numbers in every rectangle.
(In fact, the most complete search has the complexity O(n^6)) =))