Fişierul intrare/ieşire:ferma2.in, ferma2.outSursă.com 2011
AutorMihai-Alexandru DusmanuAdăugată decezar305Mr. Noname cezar305
Timp execuţie pe test0.3 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ferma2

Criza l-a lovit inclusiv pe batranul nostru prieten, fermierul Ion. Ramanand fara banii necesari intretinerii fermei, s-a hotarat sa vanda parcele in decursul a K zile. Terenul lui Ion este de forma unui triunghi dreptunghic isoscel de cateta N, alcatuit din patrate 1×1, fiecare dintre acestea avand valori diferite la vanzare.

Fiindu-i frica de FISC, fermierul s-a hotarat sa vanda exact o parcela pe zi. Pentru a nu atrage atentia vecinilor, parcela trebuie sa fie una din laturile terenului actual, dupa cum este prezentat in figura de mai jos:

Ajutati-l pe prietenul nostru sa obtina din vanzarea parcelelor profitul maxim posibil, fara ca FISC-ul sau vecinii invidiosi sa-l detecteze.

Date de intrare

Fişierul de intrare ferma2.in va contine pe prima linie numerele N si K. Pe urmatoarele N linii este data configuratia gradinii: linia i + 1 va contine i numere fiecare reprezentand valoarea parcelei respective.

Date de ieşire

În fişierul de ieşire ferma2.out se va afisa pe prima linie profitul maxim pe care il poate obtine Ion.

Restricţii

  • 1 ≤ N ≤ 1000
  • 0 ≤ K ≤ N
  • 0 ≤ profitul obtinut de Ion pentru un patrat 1×1 ≤ 100

Exemplu

ferma2.inferma2.out
5 3
82
55 3
67 46 52
62 20 54 85
66 32 40 78 52
702

Explicatie

In prima zi Ion vinde parcela cu valorile: 82 55 67 62 66. In a doua zi el vinde parcela: 3 52 85 52. In ultima zi vinde: 46 54 78. Profitul total obtinut este 82 + 55 + 67 + 62 + 66 + 3 + 52 + 85 + 52 + 46 + 54 + 78 = 702.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content