ratb
Управата
на град
Букурещ
решила да
продаде на
търг по един билборд
на всяка от n-те спирки по
маршрута на
автобусна
линия 2006. За
целта било
направено
проучване, с
цел да се
оцени
месечната
печалба, в
румънски леи,
която може да
бъде получена
от всеки билборд.
За някои
спирки,
разположени
на не много
оживени
места се
оказало, че е
възможно да
няма печалба,
а дори и
загуба
(отрицателна
печалба!). За
да продадат билбордовете
на всяка
цена,
градската
управа
решила, че
всеки
инвеститор,
който се
интересува
от подобна
покупка,
трябва да
купи поне k билборда,
разположени
на
последователни
спирки. Вашата
задача е да
определите
последователността
от билбордове,
която трябва
да купи един
инвеститор,
за да има
максимална
печалба. Ако
не е възможно
да се осигури
печалба, то поне
загубата да
бъде колкото
се може
по-малка.
Задача
Определете максималната печалба, която може да се получи от k или повече последователни билбордове, както и да се посочат номерата на първия и последния билборд от последователността, за които се достига максималната печалба. Билбордовете са номерирани с числата от 1 до n.
Вход
Входният файл ratb.in съдъдържа на първия ред целите положителни числа n и k, разделени с интервал, а на втория ред от файла са записани n цели числа, разделени с интервали, представляващи очакваната печалба за всеки един от n-те билбордове.
Изход
Изходният файл ratb.out трябва да съдържа на първия ред търсената максимална печалба, а на втория ред номерата на първия и последния билборд, от последователността, за която се достига максималната печалба. Ако има повече от една последователности, за които се достига максималната печалба трябва да бъде изведена тази, която е по близка до началото на маршрута (номерът на първия билборд е минимален; ако има повече от едно решение с минималния начален номер, трябва да бъде изведено решението, което има най-малък номер на последния билборд).
Ограничения
Примери
ratb.in |
ratb.out |
ratb.in |
ratb.out |
10 3 |
210 |
7
2 |
-11 |
ratb.in |
ratb.out |
10
3 |
30 |
Ограничение
за време: 0.1
секунди на
тест
"Titu Maiorescu" University
- Bucharest
Contact:r_boriga@yahoo.com
(Превод на
български:
Стоян Капралов)