Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Кубик - 2

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

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

Играть могут несколько человек по следующим правилам:

  1. Первым ходом игрок ставит кубик в левую верхнюю клетку поля на любую грань.
  2. Каждым следующим ходом игрок переходит на соседнюю справа или снизу клетку, перекатывая кубик на любую из 4 соседних граней.
  3. За каждый ход игрок получает K*A очков, где A - число, записанное в текущей клетке поля, K - цифра на той грани кубика, которой он стоит на игровом поле.
  4. Игрок ходит, пока не окажется в нижней правой клетке поля. Тогда очки за все его ходы суммируются.
  5. Когда один игрок закончил ходить, начинает ходить второй игрок и т.д.
  6. Победитель - игрок, набравший больше всех очков.

По заданному игровому полю определите максимальную сумму очков, которую можно получить, играя по указанным правилам.

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

Первая строка входного файла INPUT.TXT содержит разделенные пробелом числа N и M - размеры игрового поля (1 ≤ N×M ≤ 105). Далее идет N строк по M чисел, разделенных пробелами - числа, записанные в клетках игрового поля. Все числа по модулю не превышают 103.

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

В выходной файл OUTPUT.TXT выведите целое число – наибольшее количество очков, которые можно получить при оптимальной игре.

Пример

INPUT.TXTOUTPUT.TXT
13 3
1 -2 3
-4 5 -6
7 -8 9
78

Пояснение к примеру

Первоначально кубик следует установить на 6, далее вниз на 2, потом вниз на 6, вправо на 2 вправо на 6. Итого 6*1 + 2*(-4) + 6*7 + 2*(-8) + 6*9 = 78


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

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ