.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » leaves

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
leaves


Timp maxim de executie/test:
0.3 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Intr-o frumoasa zi de toamna Radu si Mars au observat ca aleea din gradina in care obisnuiesc sa se recreeze, e cam plina de frunze. S-au hotarat sa stranga toate frunzele in fix K gramezi. Aleea este in linie dreapta, iar ei si-au fixat un sistem de coordonate pe alee, cu originea la inceputul aleii.
Pe alee sunt N frunze de diferite greutati, asezate linie, la distanta 1 una fata de alta. Mai exact, prima frunza se afla la coordonata 1, a doua la coordonata 2, ... , a N-a la coordonata N. Initial cei doi se afla la coordonata N.
Operatia de strangere a frunzelor se intampla cand Radu si Mars pleaca din gradina, asa incat frunzele pot fi mutate doar spre stanga. Costul mutarii unei frunze este egal cu greutatea sa inmultita cu distanta pe care este mutata. Evident una dintre cele K gramezi va fi formata la coordonata 1, insa restul pot fi oriunde.

Cerinta

Aflati care este costul total minim pentru a strange cele N frunze in fix K gramezi.

Date de intrare

In fisierul leaves.in se afla pe prima linie doua numere naturale N si K, separate de un spatiu, cu semnificatia din enunt. Pe urmatoarele N linii se afla N numere naturale reprezentand greutatile frunzelor (pe linia i+1 se afla greutatea frunzei situate la coordonata i).

 

Date de iesire

Fisierul de iesire leaves.out va contine o singura linie pe care va fi scris costul minim pentru strangerea tuturor frunzelor in fix K gramezi.

Restrictii

  • 0 < N < 100 001
  • 0 < K < 11, K < N
  • 0 < greutatea oricarei frunze < 1 001

Exemplu

leaves.in

leaves.out

Explicatii

5 2
1
2
3
4
5

13

Cel mai bine e sa formam cele 2 gramezi in punctele 1 si 4.
Frunzele 1, 2 si 3 se aduc in punctul de coordonata 1, iar 4 si 5 se aduc in punctul de coordonata 4.
Costul total este:
1 * 0 + 2 * 1 + 3 * 2 + 4 * 0 + 5 * 1 = 13

Marius Andrei
Software engineer Google Inc
Contact:marsamg@yahoo.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2005: cuc, prime, radio, text2, honest, police, comori, patrate3, fisc, ref, pcod, zmeu, loc, nr01, scor2, judete, strict, convert, bile3, cod2, depou, auto2, tree, cat, nr3, chimie2, compress, jobs, zid, politics, onu2, ploaia, grazing, pstring, cartonase2, exp, cartoane, sir3, program, scoici, playlist, sqr, cai1, farfurii, joc1, trafic, carte, set, barbie, labirint, firma1, vile, game, donald, ambigram, dans, albinuta, rlcs, stea, submatrix, cub1, ham, sponsori, young, jokes, pizza1, albine, lot, atac1, monede1, count, exam, herbert, sudoku, bio, metro
De acelaşi autor: conflicte, cadere, na, distanta, ivv, aparitii, tabara1, stop, hanoi, logn, cuburi1, viteza, masina3, anticip, cabane, spp, regine, comoara2, perle, cuvinte1, sortari, triti
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre deque: platforma, compus, copaci, sirag, secvreg, cover, drept1, stalpi1, gropi1
surse trimise | ajutor