Cum găsește căprioara apa rece de izvor, tot așa găsesc eu banii și în vârful munților! – Jany MooRANDy
Enunț
Jany MooRANDy este șeful valutei peste țara sa MORANDIA. Pentru a-și tachina dușmanii, el a declarat următoarele: “Să bată vântul și ploaia, eu fac bani și-n Himalaya! Unde fac eu bani pachete, dușmanii culeg doar pietre!”. Pentru a le dovedi acestea, el a mers în munții Himalaya. Aceștia sunt alcătuiți din N
vârfuri, vârful i
având înălțimea H[i]
. El va construi o telecabină ce va porni din vârful 1
și va ajunge în vârful N
. Cabina va avea K
puncte de oprire (un punct de oprire este considerat un vârf) unde dușmanii săi vor culege pietre. Fie două puncte de oprire consecutive i
și j (i < j)
. Dacă H[i] ≤ H[j]
atunci dușmanii vor plăti (H[j] - H[i]) * C1
, altfel (H[i] - H[j]) * C2
, pentru a ajunge de la punctul de oprire i
la punctul de oprire j
.
Cerința
Ajutațil pe Jany MooRANDy să facă bani pachete, aflând amplasarea cea mai mică lexicografică a celor K
puncte de oprire, astfel încât dușmanii să plătească o sumă maximă de bani.
Date de intrare
Fișierul de intrare himalaya.in
conține pe prima linie numerele N, K, C1, C2
, iar pe a doua linie N
numere naturale separate prin spații.
Date de ieșire
Fișierul de ieșire himalaya.out
va conține pe prima linie K
numere, separate prin câte un spațiu reprezentând vârfurile unde se vor pune punctele de oprire.
Restricții și precizări
2 ≤ N, K, C1, C2 ≤ 500
- numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât
1000
Exemplu:
himalaya.in
5 3 2 3 4 2 5 2 4
himalaya.out
1 2 5