0154. Спортивная площадка

Input file name:	sport.in
Output file name:	sport.out
Time limit:	2 s
Memory limit:	32 megabytes

Кондопожскому ЦБК для строительства очередного грандиозного сооружения необходима ровная площадка прямоугольной формы. Но, поскольку рельеф местности холмистый, первый этап работы состоит в планировании участка, которое заключается в перемещении грунта и стоит весьма недешево.

Проделана немалая подготовительная работа. Вся территория площадки разбита на квадратные участки одинакового размера, для каждого из них задан объем грунта, избыточный ≈ со знаком +, недостающий - -. После перемещения указанных объемов площадка станет совершенно ровной. А вот откуда и куда перемещать - отдел АСУ комбината не дает точных рекомендаций. Впрочем, на этапе подготовки сметы строительных работ вполне достаточно указать связанные с планировкой участка затраты.

Для решения этой нестандартной задачи решено привлечь студентов ПетрГУ, которые надеются на вашу помощь.

Формат входного файла

Исходная информация представляет собой файл sport.in, первая строка которого содержит два целых числа - размеры m*n решетки, клетки которой составляют площадку (1 ≤ m; n ≤ 60). Далее следуют m строк по n разделенных пробелами целых чисел -100 ≤ aij ≤ 100 (1 ≤ i ≤ m; 1 ≤ j ≤ n), составляющих сведения об объемах перемещения грунта из клетки (+) или в клетку (-). Перемещение грунта осуществляется по вертикали или горизонтали в соседнюю клетку, затраты на такую операцию пропорциональны (условно ≈ равны) объему перемещаемого грунта.

Формат выходного файла

Результат расчета - целое число - минимальные затраты на выполнение работ.

Пример:

sport.in	sport.out
2 3 -50 6 -21 26 36 3	107

Source: Petrozavodsk Summer 2003. Petrozavodsk SU Contest #2, Friday, August 29

Discuss       Submit a solution



Printable version