Cerinţa

Ali Baba și cei 40 de hoți stăpânesc un deșert de formă dreptunghiulară, împărțit în n linii și m coloane, care definesc n*m sectoare. În fiecare sector se află o comoară ascunsă de Ali Baba. Se cunoaște valoarea în galbeni a fiecărei comori.

Un călător trebuie să traverseze deșertul de la Nord la Sud, trecând dintr-un sector în altul, astfel: din sectorul (i j) se poate ajunge în unul din sectoarele (i+1,j-1), (i+1,j) sau (i+1,j+1), dar fără a părăsi deșertul (ar fi omorât de oamenii lui Ali Baba). La trecerea printr-un sector, călătorul colectează comoara din acel sector.

Determinați valoarea totală maximă a comorilor pe care le poate colecta călătorul la traversarea deșertului, știind că pleacă din orice sector al liniei 1 (Nord) și se oprește în orice sector al linei n (Sud), cu respectarea condițiilor de mai sus.

Date de intrare

Fişierul de intrare comori.in conţine pe prima linie numerele n m. Următoarele n linii conțin câte m numere naturale, reprezentând valorile comorilor din fiecare sector.

Date de ieşire

Fişierul de ieşire comori.out va conţine pe prima linie numărul V, reprezentând valoarea maximă a comorilor care pot fi colectate.

Restricţii şi precizări

• 1 ≤ n,m ≤ 200
• valoarea fiecărei comori este un număr natural mai mic decât 100

Exemplu

comori.in

4 5
5 8 3 7 7 
1 1 4 5 1 
5 8 9 1 7 
5 8 6 6 9 

comori.out

29

Explicație

Un traseu prin care se colectează comori în valoare de 29 galbeni este:

#include <bits/stdc++.h>
using namespace std;

ifstream cin("comori.in");
ofstream cout("comori.out");

int n , m , a[204][204] , s[204][204];

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; j++)
            cin >> a[i][j];

    for(int i = 1 ; i <= n ; ++i)
        s[1][i] = a[1][i];

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; ++j)
        {
            s[i][j] = a[i][j] + max(max(s[i - 1][j-1], s[i - 1][j]) , s[i - 1][j + 1]);
            //cout << s[i][j] << " " << i << " " << j << '\n';
        }

    int pmin  = 1;
    for(int j = 2 ; j <= m ; ++j)
        if(s[n][j] > s[n][pmin]) pmin = j;

    cout << s[n][pmin];
    return 0;
}