| Fişierul intrare/ieşire: | partii.in, partii.out | Sursă | PreOJI 2017 |
| Autor | Marius Nicoli | Adăugată de |  Popa Mihai •mihaipopa12 |
| Timp execuţie pe test | 0.45 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Partii
În munţii Bucegi se doreşte amenajarea unor pârtii de schi. Zona este dreptunghiulară, cu N linii şi M coloane şi în fiecare punct dintre cele N*M se cunoaşte altitudinea. Trebuie ales un punct de start şi toate pârtiile se vor construi începând din acel punct. O pârtie se construieşte în inie dreaptă, cât timp traseul ce pleacă din acel punct este strict descrescător. Astfel, din punctul ales se pot construi maxim 4 pârtii (una care porneşte în sus, una care porneşte în jos, una în stânga şi una în dreapta).
Să se determine o modalitate de a construi pârtii cu suma lungimilor maximă.
Date de intrare
În fişierul partii.in, pe prima linie sunt două numere, N şi M separate printr-un spaţiu. Pe fiecare dintre următoarele N linii sunt câte M numere naturale sepatare prin câte un spaţiu.
Date de ieşire
În fişierul partii.out se va afişa numărul maxim de puncte care pot fi acoperite de pârtii.
Restricţii
- 1 ≤ N, M ≤ 1000
- Valorile punctelor sunt numere naturale intre 0 si 1000000000
Exemplu
| partii.in | partii.out |
|---|---|
| 3 5 1 2 3 4 4 2 4 3 2 2 2 2 2 2 4 | 6 |
Explicaţie
Stabilind punctul de pornire la coordonatele 2, 2 soluţia este formată din elementele îngroşate.
