MaxSum (bütün sütunları ziyarət et)
Düzbucaqlı bir cədvəl var, ölçüsü N sətir və M sütun. Hər bir hüceyrədə tam ədəd yerləşdirilib. Cədvəldə yuxarıdan aşağıya doğru hərəkət edə bilərsiniz. Yuxarı sətirdən istənilən hüceyrədən başlayaraq, hər dəfə "aşağıdakı qonşu" hüceyrələrdən birinə keçmək mümkündür. Yəni, (i, j) nömrəli hüceyrədən (i+1, j-1), (i+1, j) və ya (i+1, j+1) nömrəli hüceyrəyə keçə bilərsiniz. j=M halında sonuncu üç variantdan biri mümkün olmur, j=1 halında isə birinci variant mümkün deyil. Marşrutu aşağı sətirdəki istənilən hüceyrədə tamamlamaq olar.
Hər bir sütundan ən azı bir dəfə keçən bütün icazə verilən yollar arasında, keçilən hüceyrələrin dəyərlərinin mümkün olan maksimum cəmini tapacaq bir proqram yazın.
Giriş verilənləri
Birinci sətirdə N və M - sətirlərin və sütunların sayı (2 ≤ N ≤ 1024, 2 ≤ M ≤ 768, N ≥ M) verilir. Daha sonra növbəti N sətirdə məhz M boşluqla ayrılmış tam ədədlər yazılıb, bunlar cədvəlin hüceyrələrinin dəyərləridir və modulu 10^6-dan çox deyil.
Çıxış verilənləri
Tək bir ədəd çıxarın - bütün sütunlardan keçən yollar arasında tapılan maksimum cəmi.
Qeyd: Cavab 28 = 15+5+2+6-ya bərabərdir, çünki daha böyük cəmi olan bütün yollar bütün sütunlardan keçmir.
Diqqət yetirin ki, məsələdə giriş faylının ölçüsü böyükdür. C++-da sinxronizasiya ilə cin istifadə etmək tövsiyə edilmir, Java-da isə Scanner istifadə etmək tövsiyə edilmir - bu, proqramın giriş məlumatlarını oxumağa çatmamasına səbəb ola bilər.