Fişierul intrare/ieşire:zmax.in, zmax.outSursăONI 2013 baraj gimnaziu
AutorNistor-Eugen MotAdăugată deMarcelaMarcela Marcela
Timp execuţie pe test1.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.inzmax.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici