O suprafață de teren de formă dreptunghiulară este divizată în N
fâșii orizontale și M
fâșii verticale, de lățimi egale. Se formează astfel N x M
zone de formă pătrată, cu latura egală cu o unitate. Astfel, suprafața este reprezentată sub forma unui tablou bidimensional cu N
linii și M
coloane, în care pentru fiecare zonă este memorat un număr ce reprezintă altitudinea zonei respective. Interesant este că în tablou apar toate valorile 1
, 2
, …, N•M
. Suprafața este destinată turismului. Deoarece spre laturile de Est și Sud ale suprafeței există peisaje de o frumusețe uimitoare, se dorește găsirea unor trasee turistice în care deplasarea să se realizeze cu pași de lungime unitară mergând doar spre Est și spre Sud. O comisie, care trebuie să rezolve această problemă, a stabilit că un traseu este atractiv dacă și numai dacă ultima poziție a traseului are altitudinea mai mare decât prima poziție a traseului. Un traseu poate începe, respectiv se poate încheia, în oricare dintre zonele terenului, cu respectarea condițiilor anterioare.
Cerința
Se cere să se determine numărul maxim Z
de zone pe care le poate avea un traseu atractiv.
Date de intrare
În fișierul de intrare traseu.in
se află scrise pe prima linie numerele N
și M
, cu semnificația din enunț. Pe fiecare dintre următoarele N
linii se află scrise câte M
numere naturale, reprezentând, elementele tabloului bidimensional precizat în enunț. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.
Date de ieșire
În fișierul de ieșire traseu.out
se va scrie numărul Z
, cu semnificația din enunț. Dacă nu există niciun traseu atractiv, atunci se va scrie 0
.
Restricții și precizări
1 ≤ N ≤ 500
1 ≤ M ≤ 500
- Pentru teste în valoare de
40
de puncte,N ≤ 50
. - În concurs s-au acordat
10
puncte din oficiu. Aici s-au acordat pentru exemplele din enunț.
Exemplul 1:
traseu.in
3 4 12 11 10 6 7 5 4 3 9 2 8 1
traseu.out
4
Explicație
Traseele atractive de lungime 2
sunt: 7-9
, 4-8
, 2-8
.
Traseele atractive de lungime 3
sunt: 5-2-8
, 5-4-8
.
Traseele atractive de lungime 4
(maximă) sunt: 7-5-4-8
, 7-5-2-8
, 7-9-2-8
.
Exemplul 2:
traseu.in
3 3 5 8 7 9 6 4 3 1 2
traseu.out
3
Explicație
Traseele atractive de lungime 2
sunt: 5-8
, 5-9
, 1-2
.
Traseele atractive de lungime 3
(maximă) sunt: 5-9-6
, 5-8-6
, 5-8-7
.