| Fişierul intrare/ieşire: | ferma2.in, ferma2.out | Sursă | .com 2011 |
| Autor | Mihai-Alexandru Dusmanu | Adăugată de |  Mr. Noname •cezar305 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | ferma2.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.
