Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1748. Хомяки
МоделированиеДинамическое программирование и запоминающие функции
Олимпиадные задачи на русском языке
| 25/06/2012 | Лето 2012 - дорешивание ( 3G) |
| 27/06/2012 | Лето 2012 - 3 (G) |
| 02/03/2023 | Базовый уровень: динамическое программирование 2 (проводит BOGAT) (H) |
| 05/03/2024 | Динамическое программирование 2 (проводит BOGAT) (I) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В поисках пропитания большая дружная семья кроликов добрела до морковного поля.
К сожалению, чуть раньше сюда же прибыла большая дружная семья голодных хомяков.
Во избежание конфликта было решено собирать урожай по очереди. Поле представляет собой `N` грядок
по `M` кустов; на каждом кусте растет некоторое количество морковок. Очередной собирающий стартует
от любого куста первой грядки и движется к последней, переходя от одного куста к другому по
следующему правилу: от куста номер `K` на грядке `L` можно перейти только на грядку `L+1` к одному из
трех кустов с номерами `K-1`, `K`, `K+1` (конечно, если кусты с такими номерами есть).
Каждый посещенный куст очищается от моркови полностью. Первым на сбор урожая выходит один из кроликов,
следом идет хомяк, потом снова кролик и так до тех пор, пока на поле есть хоть одна морковка.
Кролики суетливы, поэтому они выбирают путь наиболее выгодный внешне: стартуют от
самого богатого куста первой грядки, а из трех последующих вариантов всегда выбирают
самый большой куст (при наличии нескольких кустов с одинаковым числом морковок
выбирается куст с наибольшим номером). Хомяки, прибыв на поле раньше, успели составить
подробную карту поля и поддерживают её в актуальном состоянии на основе оперативных
данных о сборе урожая, поэтому они для каждого хомяка выбирают путь, позволяющий
собрать максимальное количество морковок из возможных (при наличии нескольких
вариантов с максимально возможным количеством морковок выбирается путь через куст с наибольшим номером).
По известной карте поля определите, сколько моркови удалось собрать кроликам и хомякам по отдельности.
Первая строка входного файла содержит число тестов. Каждый тест начинается с двух целых чисел `N` и `M`
(`1\ ≤\ N,\ M\ ≤\ 100`). Следом идут `N` строк, в каждой из которых `M` чисел `X_{i,j}` (`0\ ≤\ X_{i,j}\ ≤\ 10`).
`X_{i,j}` – количество морковок на `j`-ом кусте `i`-ой грядки.
Для каждого теста на отдельной строке выведите через пробел два числа: количество морковок,
собранных кроликами и хомяками, соответственно.
Пример ввода
2 3 3 1 1 2 1 1 1 10 1 1 4 4 1 1 1 2 1 1 1 1 1 1 1 1 10 10 1 1
Пример вывода
7 12 18 17
