Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Хомяки и кролики

(Время: 1 сек. Память: 16 Мб Сложность: 48%)

В поисках пропитания большая дружная семья кроликов добрела до морковного поля. К сожалению, чуть раньше сюда же прибыла большая дружная семья голодных хомяков. Во избежание конфликта было решено собирать урожай по очереди. Поле представляет собой N грядок по M кустов; на каждом кусте растет некоторое количество морковок. Очередной собирающий стартует от любого куста первой грядки и движется к последней, переходя от одного куста к другому по следующему правилу: от куста номер K на грядке L можно перейти только на грядку L+1 к одному из трех кустов с номерами K-1, K, K+1 (конечно, если кусты с такими номерами есть). Каждый посещенный куст очищается от моркови полностью. Первым на сбор урожая выходит один из кроликов, следом идет хомяк, потом снова кролик и так до тех пор, пока на поле есть хоть одна морковка.

Кролики суетливы, поэтому они выбирают путь наиболее выгодный внешне: стартуют от самого богатого куста первой грядки, а из трех последующих вариантов всегда выбирают самый большой куст (при наличии нескольких кустов с одинаковым числом морковок выбирается куст с наибольшим номером). Хомяки, прибыв на поле раньше, успели составить подробную карту поля и поддерживают её в актуальном состоянии на основе оперативных данных о сборе урожая, поэтому они для каждого хомяка выбирают путь, позволяющий собрать максимальное количество морковок из возможных (при наличии нескольких вариантов с максимально возможным количеством морковок выбирается путь через куст с наибольшим номером).

По известной карте поля определите, сколько моркови удалось собрать кроликам и хомякам по отдельности.

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

В первой строке входного файла INPUT.TXT содержится два целых числа N и M (1 ≤ N, M ≤ 100). Следом идут N строк, в каждой из которых M чисел Xi,j (0 ≤ Xi,j ≤ 10). Xi,j - количество морковок на j-ом кусте i-ой грядки.

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

В выходной файл OUTPUT.TXT выведите через пробел два числа: количество морковок, собранных кроликами и хомяками, соответственно.

Примеры

INPUT.TXTOUTPUT.TXT
13 3
1 1 2
1 1 1
10 1 1
7 12
24 4
1 1 1 2
1 1 1 1
1 1 1 1
10 10 1 1
18 17

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483