== include(page="template/taskheader" task_id="traseu") ==
Poveste și cerință...
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.
h2. Date de intrare
Fișierul de intrare $traseu.in$ ...
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.
h2. Date de ieșire
În fișierul de ieșire $traseu.out$ ...
Î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.)
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ M ≤ 500$
* $1 ≤ N ≤ 500$
* $1 ≤ A[i][j] ≤ 1000$
h2. Exemplu
table(example).
|_. traseu.in |_. traseu.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2 3
1 10 20
11 2 3
| 34
|
h3. Explicație
...
Traseul optim trece prin zonele (1,1), (1,2), (1,3), (2,3).
== include(page="template/taskfooter" task_id="traseu") ==
