Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Maxsum
Задача Maxsum  
         
Журі думає, що вам доводилося розв’язувати таку задачу:
«Є  прямокутна таблиця розміром M рядків на N стовпців. У кожній клітинці записано ціле число. По ній потрібно пройти згори  вниз, починаючи з якої-небудь клітинки  верхнього рядка, далі кожного разу переходячи в одну з «нижньо-сусідніх» клітинок  (іншими словами, з клітинки з номером (i, j) можна перейти або на  (i+1, j-1), або на  (i+1, j), або на  (i+1, j+1); в разі j=N можливі лише 1-й і 2-й з трьох перерахованих варіантів, в разі j=1 - лише 2-й і 3-й) і закінчити маршрут в якій-небудь клітинці нижнього рядка.
     Напишіть програму, яка знаходитиме максимально можливу суму значень пройдених клітинок серед усіх допустимих шляхів»
     Розв’яжіть   дану задачу при додатковому обмеженні: допускаються лише шляхи, які проходять (хоча б по одному
разу) через всі стовпчики.
 Технічні умови
Программа Maxsum читає з клавіатури M і N -  кількість рядків і кількість стовпців (2<= M<= 200,  2<= N<= 40,  M>=N), далі в кожному з подальших M рядків зчитується  рівно по N розділених пропусками цілих чисел (кожне не перевищує по модулю 1000000) - значення клітинок таблиці. Програма виводить на екран єдине число-  шукану величину.
Приклад
 
Введення
4 3
1 15 2
9 7 5
9 2 4
6 9 -1
Виведення
28  

© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"