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

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


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

Fie două şiruri de lungime N de numere întregi a1, a2, ..., aN şi respectiv b1, b2, ..., bN.
Alegând anumiţi indici 1 <= i1 < i2 < … < ik <= N, formăm sumele Sa = ai1 + ai2 + … + aik şi Sb = bi1 + bi2 + ... + bik.

Cerinţă

Să se determine suma Sa maximă care se poate obţine alegând şirul de indici i1, i2, ..., ik astfel încât suma Sb să nu fie negativă.

Date de intrare

Fişierul de intrare siruri3.in conţine pe prima linie un număr natural N reprezentând lungimea şirurilor. Urmează N linii. Linia i+1 va conţine valorile ai şi bi separate printr-un spaţiu.

Date de ieşire

Fişierul de ieşire siruri3.out va conţine un singur număr natural reprezentând suma maximă Sa care se poate forma astfel încât suma Sb să nu fie negativă.

Restricţii

  • 3 <= N <= 1000
  • Valorile memorate în siruri sunt numere întregi cuprinse între -100 şi 100
  • Se garantează că pentru datele de intrare se poate obţine o soluţie validă cu Sb >= 0

Exemple

siruri3.in siruri3.out Explicaţii
3
1 -5
-4 8
1 -1
-2 Şirul a este: 1 -4 1
Şirul b este: -5 8 -1
Suma maximă se obţine alegând toate numerele:
Sa = 1 + (-4) + 1 = -2
Sb = (-5) + 8 + (-1) = 3 >= 0
siruri3.in siruri3.out Explicaţii
5
-1 -3
7 -3
-1 8
5 -11
3 -1
9 Suma maximă se obţine alegând numerele de pe poziţiile 2, 3, 5:
Sa = 7 + (-1) + 3 = 9
Sb = -3 + 8 + (-1) = 4 >= 0

student Gabriel Mititelu şi student Andrei Bistriceanu
Vrije Universiteit Amsterdam
gaby.miti@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la XOR 2011: triunghi3, cmmdcsecv, drumuri1, fillmat, secvb
De acelaşi autor: cai, rebus, harta, comun, axa, sir, ocean14, reduceri, div3, patrate6, vot, reziduu, accesibil, predecesor, permutari, scanduri, ordonare, xor1, paltrei, triunghi1, 123, traseu1, parbit, petrecere, secvbiti, subm, triunghi3, cmmdcsecv, drumuri1, fillmat, secvb, acces, segmente, echilibru1, broscute, ksecv, paisprezece, proddiv, perechi2, expeval, maxtri, combcuv, dfs, qtri, blis, maxbin, probleme, divider, eliminare, minm, genab, grafxy, matd3, azeval, matrixdel, speed, maxp, split, binremove, sminus, subsets, tcif, sprime, sir2dif, ecp, arbsum, robotzi, permtr, unudoi, matcnt, ssdj, dominant
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, ratb, 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, 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
surse trimise | ajutor