Fișierul intrare/ieșire	zmax.in, zmax.out	Sursă	ONI 2013 baraj gimnaziu
Autor	Nistor-Eugen Moț	Adăugată de	Marcela • Marcela
Timp de execuție pe test	1.5 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	4

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Zmax (baraj gimnaziu)

Se consideră o matrice cu M linii și N coloane. În fiecare celulă (element) a matricei este memorat câte un număr întreg. Numim „Z” o mulțime de celule din matrice formată dintr-un grup de celule consecutive, situate pe aceeași linie, legate printr-un șir de celule, situate în diagonală (pe direcția Nord-Est -> Sud-Vest), de un alt grup de celule consecutive situate pe o altă linie a matricei, neadiacentă (neconsecutivă) cu prima linie (adică între linia de sus și cea de jos a unui “Z” să mai existe cel puțin încă o linie a matricei).
Un astfel de „Z” îndeplinește condițiile:
• fiecare dintre cele două linii orizontale ale „Z”-ului are cel puțin două celule;
• diagonala începe cu celula cea mai din dreapta a liniei de sus a „Z”-ului, fiecare dintre celulele următoare se află imediat în stânga și în jos față de cea anterioară, ultima celulă a diagonalei este cea mai din stânga celulă a liniei de jos a „Z”-ului.
Dintre imaginile următoare, doar imaginea E conține un „Z”:

Asociem fiecărui astfel de „Z” un cost egal cu suma numerelor memorate în celulele care alcătuiesc „Z”-ul.

Cerință

Scrieți un program care să citească numerele naturale M și N, cele MxN numere memorate în celulele matricei și să determine cel mai mare cost al unui „Z” din matrice.

Date de intrare

Fișierul de intrare zmax.in conține pe prima linie numerele naturale M și N, separate printr-un spațiu. Pe fiecare dintre următoarele M linii se găsesc câte N numere întregi, separate de câte un spațiu.

Date de ieșire

Fișierul de ieșire zmax.out va conține pe prima linie un singur număr întreg reprezentând cel mai mare cost al unui „Z” din matrice.

Restricții

• 3 ≤ M, N ≤ 500;
• Numerele memorate în celulele matricei sunt numere întregi din intervalul închis [-10000,10000].

Exemplu

zmax.in	zmax.out	Explicații
5 4 3 -5 -2 4 -2 7 1 -3 1 1 1 1 2 -3 2 -3 3 -2 1 -4	10	3 -5 -2 4 -2 7 1 -3 1 1 1 1 2 -3 2 -3 3 -2 1 -4 Matricea are 5 linii și 4 coloane și conținutul din imaginea alăturată. Cel mai mare cost care poate fi asociat unui „Z” din matrice(„Z” -ul din imagine) este 10.