Fişierul intrare/ieşire:partii.in, partii.outSursăPreOJI 2017
AutorMarius NicoliAdăugată demihaipopa12Popa Mihai mihaipopa12
Timp execuţie pe test0.9 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inpartii.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?