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

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


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

Primaria municipiului Bucuresti a hotarat sa scoata la licitatie cate un chiosc in fiecare dintre cele n statii de pe traseul autobuzului 2006. In acest scop Primaria a efectuat un studiu de fezabilitate cu ajutorul caruia a fost estimat profitul lunar, in RON, ce poate fi obtinut de catre fiecare chiosc. In unele statii, aflate in zone mai putin circulate, s-a constatat ca este posibil sa nu se obtina nici un profit, ci chiar sa se inregistreze pierderi (adica profitul sa fie negativ!). Pentru a putea sa vanda totusi toate chioscurile, Primaria a hotarat ca fiecare investitor interesat sa fie obligat sa cumpere chioscurile aflate in cel putin k statii consecutive. Sarcina voastra este sa determinati secventa de chioscuri pentru care trebuie sa liciteze un investitor astfel incat profitul estimat sa fie maxim. Deoarece orice investitor doreste sa pastreze relatii cordiale cu Primaria, in cazul in care nu exista nici o secventa de chioscuri care sa aduca profit el va licita pentru o secventa de chioscuri pentru care pierderile sunt minime.

Cerinta

Fiind date numerele naturale n si k sa se determine profitul maxim ce poate fi obtinut pentru o secventa formata din cel putin k chioscuri dintre cele n, precum si numerele de ordine ale primului, respectiv ultimului chiosc din secventa pentru care se obtine profit maxim. Chioscurile se considera numerotate de la 1 la n.

Date de intrare

Fisierul de intrare ratb.in contine pe prima linie numerele n si k, despartite printr-un spatiu, iar pe a doua linie n numere intregi, separate prin spatii, reprezentand in ordine profiturile estimate pentru cele n chioscuri.

Date de iesire

Fisierul de iesire ratb.out va contine pe prima linie profitul maxim cerut, iar pe a doua linie numerele de ordine ale primului, respectiv ultimului chiosc din secventa pentru care se obtine profitul maxim. Daca exista mai multe secvente pentru care profitul este maxim se va considera aceea care se afla cat mai aproape de inceputul traseului (chioscul de inceput sa fie minim; in cazul in care exista mai multe solutii cu chioscul de inceput minim, se va alege solutia care are si chioscul de sfarsit minim).

Restrictii

  • 1<=k<=n<=5000
  • Profitul estimat pentru fiecare chiosc este un numar intreg nenul cuprins intre -1000 si 1000.

Exemple

ratb.in

ratb.out ratb.in ratb.out

10 3
23 -70 -73 82 -6 49 85 -118 37 26

210
4 7
7 2
-35 -12 -60 49 -80 -100 -20
-11
3 4

 

ratb.in ratb.out
10 3
-100 10 10 10 -70 10 10 10 -50 -20

30
2 4

lect. drd. Radu Boriga
Universitatea "Titu Maiorescu" - Bucuresti
Contact:r_boriga@yahoo.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2006: scara, programs, nr, iepuras2, numere3, robot2, fry, suma, sah, formule, perm, cifra, repeat, ture, xor, policefm, unu, criptare, ed, bilete, vector, scor, infinit, race, dragon, kreg, placi, hanoig, red, 2sec, flood, sume3, balls, festival, croco, johnie, matrice3, pavaj, sume, arthur, kimberley, kafka, vocale, pento, prop, ro, sol, bacan, erdos, poligon, reduceri, druid, novel, gramezi, nrbinar, laser, spair, caravane, cuburi, grup, invest, cd, friends2, mese, toys
De acelaşi autor: cifra, policefm, festival, kafka, laser, prime, bile3, chimie1, livada1, minerale
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
Despre secvenţe: degrade, hora, simetric, egal, ruleta, ecran, sirag, pasi, firma, br, numere2, termen, div, teatru, repeat, 2sec, sport, pikachu, suma3, panouri, sir5, mare, hof, resturi, efort, xor1, livada1, diff, popic, guess, albine1, permutare, miere, atelier, obstacole, echilibru1, lcdr, 3max, ksecv, maxbin, meteo1, galbeni, maxp, secvp, split, secvente2, ausoara, sminus, munte3, cool, betisoare, unudoi, charlie, lasere, arc, dominant, restaurare, roua
surse trimise | ajutor