Fişierul intrare/ieşire: | traseu.in, traseu.out | Sursă | Olimpiada pe scoala 2015 |
Autor | clasica | Adăugată de | |
Timp execuţie pe test | 0.1 sec | Limită de memorie | 2048 kbytes |
Scorul tău | N/A | Dificultate |
Traseu (clasele 11-12)
Sătul de atâtea olimpiade şi concursuri, Algorel a plecat la munte, să se relaxeze. Odată ajuns acolo s-a hotărât să urmeze un traseu cu peisaje cât mai frumoase. El are la dispoziţie o hartă codificată sub forma unei matrice cu M linii şi N coloane, ale cărei elemente sunt numere naturale nenule reprezentând gradul de frumuseţe corespunzător fiecărei zone (element al matricei). Algorel trebuie să plece din colţul stânga sus al matricei (poziţia (1,1)) şi să ajungă în colţul dreapta jos (poziţia (M,N)), având voie să se deplaseze doar spre dreapta şi în jos (de pe poziţia curentă (i,j) se poate deplasa fie pe poziţia (i+1,j), fie pe poziţia (i,j+1)). Definim gradul de frumuseţe al unui traseu ca fiind suma gradelor de frumuseţe ale elementelor matricei care-l compun. Se cere găsirea gradului maxim de frumuseţe pe care îl poate avea un traseu care respectă restricţiile de mai sus.
Date de intrare
Fişierul de intrare traseu.in conţine pe prima linie două numere naturale nenule M şi N. Pe următoarele M linii se află câte N numere naturale nenule, separate prin câte un spaţiu, reprezentând elementele matricei A, care codifică harta.
Date de ieşire
În fişierul de ieşire traseu.out se va scrie un singur număr S reprezentând gradul maxim de frumuseţe pe care îl poate avea un traseu care respectă restricţiile de mai sus. (Gradul de frumuseţe al unui traseu este suma gradelor zonelor din matrice care îl compun.)
Restricţii
- 1 ≤ M ≤ 500
- 1 ≤ N ≤ 500
- 1 ≤ A[i][j] ≤ 1000
Exemplu
traseu.in | traseu.out |
---|---|
2 3 1 10 20 11 2 3 | 34 |
Explicaţie
Traseul optim trece prin zonele (1,1), (1,2), (1,3), (2,3).