Есть матрица размером n на m, заполнена нулями и единицами. Нужно найти найбольший по площе прямоугольник, который содержит только единицы. Если можно, подскажите с решением и возможно местом, где эта задача находится на онлайн ресурсе.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 11.11.2026 01:30:51 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
быть может это поможет Вам: Your text to link here...
спасибо, после 40 минут просмотра и разбора я вроде бы понял эту статью. Но у меня созрел вопрос: чем отличается stack от vector-а? Вроде бы и там и там с одной стороны засовывают и с одной забирают.
Меня часто пытаются переубедить, но мне кажется, что std::stack побыстрее, чем std::vector. Всё-таки std::stack — это не урезанная версия std::vector, и было бы логично реализовать структуру с меньшим функционалом оптимальнее, чем со сложным.
(Правда, это урезанная версия std::deque...)
Лол. Что там убеждать-то, и так видно.
http://codeforces.me/contest/490/submission/8894056 http://codeforces.me/contest/490/submission/8894061
Разница только в параметрах шаблона стека в дереве фенвика. По умолчанию при чем там deque, если не указать иное.
P.S. На segment_tree_t не смотри, он с прошлых посылок остался, с ним даже со вектором внутри стека не заходит.
Было бы логично, но так не делают.
Сравнение не совсем корректно.
std::stack не контейнер, а адаптер. Стандартные контейнеры это std::list, std::vector и std::deque. "Под капотом" у стека всегда есть какой-то контейнер, по умолчанию в g++ это deque.
То есть по сути сравнивая stack и vector ты сравниваешь deque (при условии того, что его пользуют как стек) и vector (при тех же условиях).
В чём же заключается сложность функционала std::vector?
Если нужны только операции взятия и удаления, то лучше использовать стек, ИМХО
Вектор только если нужны еще какие-либо функции
где эта задача находится на онлайн ресурсе"Чистую" задачу я не нашёл, но вот эта задача сводится к поиску максимальной подматрицы.
Вот похожая задача на топкодере: ссылка
сайт contest.bsuir.by там [Practice. Dynamic programming] problem I
сайт [practice.Dynamic programming], задача I.мистер средний
ACMP — фермер 2
вот, спасибо, когда-то решал эту задачу, вспоминал о ней, но не мог найти ее и своего решения. Но решал я эту задачу и совсем не так, как написано на е-максе, а так: линк. Но думаю, для прямоугольников такой метод не прокатит.
Хотя если хранить в каждой клетке динамики 2 стороны прямоугольника, то наверное может пройти.