[Logo] Форум DL
  [DL]  На главную страницу 
Индекс форума ->Олимпиадное программирование ->Обсуждение Sphere-задач
Автор Сообщение
Руслан Коржик

Темы: 14
Сообщений: 86

Мой профиль
Мне удалось придумать решение за N2logN. Кто-нибудь придумал решение лучше? Мое прошло за 2.9 сек.(ограничение 3).

Вкратце условие: есть поле со свободными и занятыми клетками, надо вписать туда прямоугольник максимальной площади (мне эта задача напомнила задачу про амбар фермера Джона)

Условие: Rus
Eng
Руслан Коржик

Темы: 14
Сообщений: 86

Мой профиль
Что-то никто не отвечает

Интересно, как решали Гена и Вова?
http://www.spoj.pl/status/CTGAME,tourist/
http://www.spoj.pl/status/CTGAME,vovamin/
8)

Геннадий Короткевич

Темы: 6
Сообщений: 37

Мой профиль
N2logN. 0.5 сек 8)
Возможно, у тебя не очень хорошая реализация или не очень эффективная идея решения...
Можешь рассказать идею своего решения?
______________________
Nothing is impossible; impossible itself says: "I m possible"...
Руслан Коржик

Темы: 14
Сообщений: 86

Мой профиль
Странно. У меня только чтение из файла работало за 0.5. Наверное особенности реализации
А нельзя посмотреть исходник?
Владимир Миняйлов

Темы: 9
Сообщений: 30

Мой профиль
Можно за O(N^2).
После рассмотрения i строк высота или увеличиваеться на 1 или меняеться на 0 => можно сортить за O(N). Далее просто просчет(нарпимер, двусвязным списком).
P.S. Я слышал, что такую задачу можно решать на основе стека. Но не знаю как...
 
Индекс форума ->Олимпиадное программирование ->Обсуждение Sphere-задач
Time:0,036