<ПРЕД Задача:
СЛЕД>
Задачу решили 558 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Космический зоопарк

Time limit = 5 секунд(ы)

Memory limit = 33000 Kb

Шёл 2130-й год. Колонисты с планеты Земля приземлились на одну из планет системы Альфа Центавра. Их миссия состояла в исследовании ближайших звёзд и планет. Основав несколько космических поселений, они сформировали высокоразвитое общество. Теперь, 14 лет спустя, они обнаружили, что в некоторых ближайших галактиках существует жизнь. К тому же галактики, в которых обнаружена жизнь, расположены так, что образуют 3-хмерную прямоугольную матрицу. Вы можете полагать, что существует прямоугольный параллелепипед, разделённый на ячейки по 1 галактике в каждой ячейке. Измерения параллелепипеда — целые числа M, N и D, причём 1 ≤ M,N,D ≤ 20, а каждая ячейка — это куб со стороной 1. Правительство Альфа Центавра решило построить космический зоопарк. Формы жизни в различных галактиках различны, поэтому если галактика становится частью зоопарка, то она получает некоторую прибыль (которая различна для разных галактик). Главный экономист космического поселения мистер Иванофф подсчитал годовую прибыль для каждой галактики. Современные технологии строительства космических объектов требуют, чтобы космический зоопарк был прямоугольным параллелепипедом со сторонами, параллельными сторонам параллелепипеда, ограничивающего галактики. Имея результаты подсчётов, которые проделал мистер Иванофф, определите наибольшую прибыль (или наименьший убыток), которую может получить правительство Альфа Центавра от строительства такого зоопарка.

Зная числа в ячейках, на которые разбит прямоугольный параллепипед, вмещающий рассматриваемые галактики, определите содержащийся в нём параллелепипед с максимальной суммой чисел в нём. Вы можете считать, что сумма чисел в любом таком включённом параллепипеде меньше 32000.

Вход В первой строке содержится 3 числа: M, N, D, такие что 1 ≤ M,N,D ≤ 20. Далее следует D блоков, каждый блок содержит M строк по N целых чисел, представляющих собой прибыль соответствующих галактик. Значения прибылей или убытков (что соответствует отрицательной прибыли) по величине не превосходят 500.

Выход Вывод должен содержать одно число — максимально возможную прибыль (или минимальный убыток).

Вход#1
1 1 1
1
Выход#1
1

Вход#2
2 2 2

2 -1
-2 2

-2 2
2 -1
Выход#2
2

Вход#3
2 2 2

-2 -3
-5 -4

-6 -7
-9 -8
Выход#3
-2

Вход#4
2 3 4

1 1 1
1 1 1 

1 -1 1
1 1 1 

1 -1 1
1 1 1 

1 1 1
1 1 1
Выход#4
20

Автор:
Idea by Smolyakov Andrey & Alex
Desctiption and tester by Malyh Anton.

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 3.228.10.17