| 1 Оглуздин Дмитрий Сергеевич, 01 декабря 2025 г. 23:00:56 |
| насколько я понимаю, один из быстрейших алгоритмов для этой задачи это O(n*n*m) либо O(n*m*m), не так принципиально (кому интересно почитайте про алгоритм Джея Кадана), хорошая задачка, полезная очень ! если собираетесь использовать этот алгоритм учтите, в условии длина подматрицы не может равнятся нулю, тоесть надо рассмотреть случай если все числа в матрице отрицательны !
|
|
|
| 2 Арестович Егор Викторович, 09 апреля 2025 г. 20:39:12 |
| Решил за O(N^2*M^2). Недавно на олимпиаде была 1в1 задача, только ограничения были огромные, и соответственно решение должно было быть за O(N*M), знаю, что такое решение есть, но как его написать, совсем не думается
|
|
|
| 3 Кактус, 21 июля 2022 г. 14:55:45 |
| Админ, сделайте такую же но с ограничением N, M до 10000 и пару тестов. Путь некто сильно умный решит, и люди поверят что ее можно решить за N*M!)))
|
|
|
| 4 Матус Даниил Дмитриевич, 12 августа 2020 г. 21:54:36 |
| сдал за n*n*m*m прошло за 0.12 как так народ
|
|
|
| 5 МИРЖАХОН КАЙИМОВ МИРТЕМИРОВИЧ, 05 июня 2020 г. 8:04:39 |
| Задача легко решается со сложностью O(M*N*M*N) 0.874c v pascale
|
|
|
| 6 Влад Федоров, 07 июля 2019 г. 14:26:32 |
| Можно за O(n*m*(n + m))
|
|
|
| 7 ГРигорий горбаченко, 25 ноября 2018 г. 20:43:39 |
| Тест который мне помог, 3 3 -10 -10 -10 -10 -10 -10 -10 -10 -10 ответ -10
|
|
|
| 8 Давид Нигматуллин, 31 августа 2018 г. 20:38:05 |
предлагаю указать, что прямоугольник с нулевой стороной, быть не может, потому что мне казалось что в крайнем случае можно ничего не брать, и получить 0
Сделано.
|
|
|
| 9 Японский шпион, 12 июля 2018 г. 5:57:26 |
| Kadane's algorithm, O(n^3).
|
|
|
| 10 Мурашов Денис Андреевич, 08 июля 2018 г. 14:27:49 |
Решение O(N^2 * M^2) не проходит по времени на Python (см. 8530435).
И не должно проходить. Python может выполнить порядка 10^6 операций в секунду, а для указанной Вами сложности получается ближе к 10^8 операций. Не все задачи можно сдать на Python.
|
|
|
| 11 Беляев Сергей Николаевич, 16 января 2016 г. 9:51:26 |
Добавлены новые тесты. Все решения перепроверены.
|
|
|
| 12 Скрынник Алексей Александрович, 09 июня 2015 г. 11:24:42 |
| Решил за O(n^3)
|
|
|
| 13 Нуриев Наиль Дамирович, 25 апреля 2015 г. 10:01:16 |
| Советую сначала решить задачу №470.
|
|
|
| 14 Костливцев Никита Алексеевич, 28 марта 2013 г. 9:37:11 |
| Прикольная задача...
|
|
|
| 15 Иванов Александр Сергеевич, 25 июля 2011 г. 23:28:04 |
Я непонимаю, как это задачу можно решить без перебора? Ведь в любом случае нам надо будет вычислить суммы абсолютно всех прямоугольников. И как же тут тогда применить динамическое программирование? Если не сложно, дайте хотя бы указание, потому что как я ни крутился, дальше 10-го теста не прошел. Можно конечно попытаться решить с помощью дерева Фенвика, но неужто иначе нельзя?
Задача имеет достаточно простое решение со сложностью O(N^2*M^2), разумеется динамическое. Но конечно никто не запрещает использовать двумерные деревья отрезков, но это как то посложнее будет ....
|
|
|
| 16 Балакший Андрей Владимирович, 22 июня 2011 г. 16:29:54 |
| Хм, придумал как решить только после задачи 470...
|
|
|
| 17 Bruce Wayne, 16 марта 2011 г. 11:22:50 |
3 3
1 1 1
1 -100 1
1 1 1
|
|
|
| 18 Нагин Сергей Юрьевич, 04 сентября 2010 г. 20:37:39 |
| так-же просто можно решить и за Куб...
|
|
|
| 19 Грачев Владимир Алексеевич, 07 октября 2009 г. 18:18:09 |
Вот уж никак не думал,что ваш сервер осилит порядка 50 миллионов за секунду,и пытался решить за Н*М,пока не прочитал обсуждение!
Да, просто операции простые, вот если бы там были умножения... Сервер наш не особо быстрый, но эта задача полезна для понимания оценки скорости простых операций. На хорошей машине может за секунду выполняться до миллиарда простых операций (например xor) :)
|
|
|
| 20 Масюк Олег Юрьевич, 22 января 2009 г. 12:25:22 |
Скажите как тут динамику применять?
Динамика тут может использоваться для вычисления промежуточных результатов. Если догадаться для каких, то применить ее совсем будет просто.
|
|
|
