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

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


Timp maxim de execuţie/test:
0.3 secunde
Memorie totală disponibilă/stivă:
16MB/1 MB

Băieţii de la 808 vor să organizeze o întrecere cu ripstick-urile. Ei au stabilit N trasee, fiecare dintre acestea având un anumit grad de solicitare, S[i] (1<=i<=N), reprezentat printr-un număr întreg. Băieţii s-au hotărât să împartă concursul în mai multe runde, între care să existe o pauză de odihnă. O rundă poate să fie formată dintr-un număr oarecare de trasee consecutive. Gradul de solicitare al rundei este egal cu suma gradelor de solicitare ale fiecărui traseu din runda respectivă. Se ştie că pauza dintre două runde poate să micşoreze gradul de solicitare al rundei anterioare, acesta luând valoarea A, doar dacă gradul iniţial se află în intervalul [A, B].

Cerinţă

Băieţii de la camera 808 vă roagă să-i ajutaţi să calculeze suma minimă a gradelor de dificultate ale tuturor rundelor.

Date de intrare

Fişierul de intrare ripstick.in conţine pe prima linie 3 numere naturale N A B cu semnificaţiile din enunţ. Pe cea de a doua linie se află N numere întregi. Al i-lea număr reprezintă gradul de solicitare S[i] al celui de al i-lea traseu.

Date de ieşire

Fişierul de ieşire ripstick.out va conţine o singură linie pe care va fi scris un număr întreg, reprezentând suma minimă obţinută.

Restricţii

  • 1 <= N <= 100 000
  • 1 < A, B <= 1 000 000 000
  • -10 000 <= S[i] <= 10 000
  • Pentru 20% din teste 1 <= N <= 1 000
  • Pentru alte 20% din teste 0 <= S[i]
  • Un traseu poate să fie mai mult relaxant decât solicitant, deci gradul de solicitare poate fi negativ.
  • Fiecare traseu trebuie să aparţină exact unei runde.

Exemplu

ripstick.in ripstick.out
4 17 27
3 12 10 9
26
Alexandru Cazacu
Facultatea de Matematică şi Informatică - Universitatea Bucureşti
alexandru.cazacu92@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2011: ore, pegals, valet, xpn, efect, nrperm, b2k, sumdivprod, nr0, maxviz, oneton, oras1, ksecv, antic, oak, nor, nrpomi, sumprod, paisprezece, cover1, prisme, gxor, progresii, anagramabil, zuma, nrpal, sdmin, lista, operatii1, codarb, codpatrat, adprod, puncte4, qtri, reconst, gsm, subsiruri, mijloc, trifoi, cubulete, romb, maxbin, albine2, probleme, triburi1, megascoala
De acelaşi autor: sdmin, triunghi5, descompunere, vectori1, drumuri2
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, leaves, 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, 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 arbore de intervale: centrala, lcdr, 3max, ksecv1
surse trimise | ajutor