Вася и матрица

@AvengerAlive · Регистрация: 30.07.2011

Студворк — интернет-сервис помощи студентам

Вася и матрица

Вася и матрица

Васе мама подарила прямоугольную матрицу N на M. В каждой ячейке матрицы записано целое число. Вася долго игрался в разные математические игры с ней: то быстро вычислял её детерминант, то с легкость возводил её в разные степени.

Но такие игры ему немного надоели, поэтому он придумал себе новое развлечение: он выбирает целое число K и пробует найти подматрицу максимальной площади, в которой сумма всех чисел не превышает K. Подматрица – это прямоугольный участок матрицы.

Технические условия

Входные данные

В первой строке заданы три целых числа N, M и K, 1 ≤ N,M ≤ 200, 1 ≤ K ≤ 109.

В последующих N строках задано по M неотрицательных целых чисел, каждое из которых не превышает 1000.

Выходные данные

Выведите единственное число – площадь максимальной подматрицы, сумма чисел в которой не превышает K.

Помогите придумать эффективный алгоритм.
Моя идея: создаю матрицу сумм. Например для матрицы
1 2 3
4 5 6
записываю
1 3 6
5 12 21

Далее просто по формуле сумм ряда вычислял рекурсией. Но лимит времени. Какую динамику можете предложить?

@iama · 10.11.2012, 10:31

Сообщение от AvengerAlive

Далее просто по формуле сумм ряда вычислял рекурсией.

Эм, а это как?

Можно ссылку на задачу, где её можно сдать? Мне кажется, перебор с одним простым отсечением может даже и зайти.

@Хохол · 10.11.2012, 18:27

Фиксируем верхнюю строку подматрицы. Фиксируем высоту подматрицы. Двумя указателями перебираем левую и правую сторону подматрицы. Куб.

@AvengerAlive · 10.11.2012, 21:41 **[ТС]**

iama, ссылочка была, модер удалил http://www.e-olimp.com/problems/3535

перебор не пройдёт. фактически я с массивом сумм провожу такой же перебор как мне описывали. надо что-нибудь однопроходное или хотя бы за n^2 m^2 А у меня получается очень много, фактически я от 1 матрицы рассматриваю 4 подматрицы сужением исходной одной из сторон и т.п.
Это работает за 4^x скажем, плохо очень.

Добавлено через 9 минут
iama,

Вот смотрите если сделать с матрицей
1 2 3
4 5 6
так
0 0 0 0
0 1 3 6
0 5 12 21
то допустим сумма той части строки где 5 и 6 вычисляется как 21-6-5+1 (все числа из новой матрицы). Так попробуйте увеличить матрицу и поискать сумму для любой подматрицы таким способом. Идея пустить рекурсию, вырубая её когда находим сумму <=k, т.к далее матрица будет уменьшаться.

@iama · 11.11.2012, 00:11

AvengerAlive, вам же Хохол правильное решение рассказал, что не так?

Не по теме:

А мой лобовик имелся в виду за четвертую степень.

@AvengerAlive · 11.11.2012, 12:46 **[ТС]**

iama, мб, но я не понял про куб.
Хохол, не могли бы чуть поподробнее рассказать что-делать? Я думал решать задачу для отрезка, поом на 2мерный случай перейти. Решать задачу для 1xM, 2xM .. NxM?

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257

	Вася и матрица 09.11.2012, 22:32. Показов 968. Ответов 5 Метки нет (Все метки) Вася и матрица Вася и матрица Васе мама подарила прямоугольную матрицу N на M. В каждой ячейке матрицы записано целое число. Вася долго игрался в разные математические игры с ней: то быстро вычислял её детерминант, то с легкость возводил её в разные степени. Но такие игры ему немного надоели, поэтому он придумал себе новое развлечение: он выбирает целое число K и пробует найти подматрицу максимальной площади, в которой сумма всех чисел не превышает K. Подматрица – это прямоугольный участок матрицы. Технические условия Входные данные В первой строке заданы три целых числа N, M и K, 1 ≤ N,M ≤ 200, 1 ≤ K ≤ 109. В последующих N строках задано по M неотрицательных целых чисел, каждое из которых не превышает 1000. Выходные данные Выведите единственное число – площадь максимальной подматрицы, сумма чисел в которой не превышает K. Помогите придумать эффективный алгоритм. Моя идея: создаю матрицу сумм. Например для матрицы 1 2 3 4 5 6 записываю 1 3 6 5 12 21 Далее просто по формуле сумм ряда вычислял рекурсией. Но лимит времени. Какую динамику можете предложить? 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	10.11.2012, 18:27
	Фиксируем верхнюю строку подматрицы. Фиксируем высоту подматрицы. Двумя указателями перебираем левую и правую сторону подматрицы. Куб. 1

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	10.11.2012, 21:41 [ТС]
	iama, ссылочка была, модер удалил http://www.e-olimp.com/problems/3535 перебор не пройдёт. фактически я с массивом сумм провожу такой же перебор как мне описывали. надо что-нибудь однопроходное или хотя бы за n^2 m^2 А у меня получается очень много, фактически я от 1 матрицы рассматриваю 4 подматрицы сужением исходной одной из сторон и т.п. Это работает за 4^x скажем, плохо очень. Добавлено через 9 минут iama, Вот смотрите если сделать с матрицей 1 2 3 4 5 6 так 0 0 0 0 0 1 3 6 0 5 12 21 то допустим сумма той части строки где 5 и 6 вычисляется как 21-6-5+1 (все числа из новой матрицы). Так попробуйте увеличить матрицу и поискать сумму для любой подматрицы таким способом. Идея пустить рекурсию, вырубая её когда находим сумму <=k, т.к далее матрица будет уменьшаться. 0

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	11.11.2012, 00:11
	AvengerAlive, вам же Хохол правильное решение рассказал, что не так? Не по теме: А мой лобовик имелся в виду за четвертую степень. 0

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	11.11.2012, 12:46 [ТС]
	iama, мб, но я не понял про куб. Хохол, не могли бы чуть поподробнее рассказать что-делать? Я думал решать задачу для отрезка, поом на 2мерный случай перейти. Решать задачу для 1xM, 2xM .. NxM? 0