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

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


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

Mirunei îi plac numerele întregi şi cărţile de joc. Într-o bună zi, pentru că se plictisea, s-a decis să inventeze un joc pentru o singură persoană. Şi-a luat pachetul de cărţi preferat şi a scris pe fiecare faţă a fiecărei cărţi câte un număr întreg. Apoi a înşirat toate cele N cărţi din pachet pe masă şi a stabilit regulile jocului:

  • Fiecare carte poate fi pusă cu oricare dintre cele două feţe în sus.
  • După ce aşează toate cărţile pe masă, acestea trebuie împărţite în două mulţimi: una de cardinal K, iar cealaltă de cardinal N-K.
  • Se adună valorile vizibile înscrise pe cărţile din prima mulţime, cea de cardinal K, şi se scad cele de pe cărţile din a doua mulţime.
  • Se doreşte maximizarea valorii obţinute.

Cerinţă

Ştiind valorile înscrise pe cărţile de joc, ajutaţi-o pe Miruna să afle răspunsul căutat.

Date de intrare

Fişierul de intrare sumdif.in conţine pe prima linie două numere întregi N şi K, având semnificaţia din enunţ. Fiecare dintre următoarele N linii va conţine câte două numere întregi, reprezentând valorile înscrise pe cele două feţe ale unei cărţi.

Date de ieşire

Fişierul de ieşire sumdif.out va conţine o singură linie pe care va fi scris un singur număr întreg, reprezentând valoarea maximă pe care o poate obţine Miruna în jocul de mai sus.

Restricţii

  • 1 ≤ N ≤ 1000
  • 0 ≤ K ≤ N
  • Valorile înscrise pe cărţile de joc vor fi din intervalul [-1000, 1000].

Exemplu

sumdif.in sumdif.out Explicatie
4 2
-5 4
9 -4
1 2
0 -10

 

26

Miruna va pune a doua şi a treia carte în prima mulţime

stud. Andrei Grigorean
Universitatea Bucuresti
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la Finala .campion 2009: autobuze, mere, circuit, cadou, kpal, chimie, sarpe, ff
De acelaşi autor: fbr, 2sir, platforma, barfa, cartonase, desen, seif, kinder, shgraf, pikachu, dist1, subgeom, submatrix1, teroristi, parpal, bubblesort
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, 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, 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 Greedy: lac, checkin, baby, startrek, placi, gramezi, mese, jobs, politics, joc3, playlist, carte, exam, subperm, piloti, barca1, pitici, bombe, pic, bac, pal, antena, culmi, numar2, lover, sant1, volei1, ab3, camion1, aranjare, popas, reactivi, mesaj2, dp, jocv, segm, calorii, album, kdtree, sport2, telecab, dag, cifre4, micro, triburi, testament, nor, eoliene, vintage, cifre5, agenda, monede2, charlie, scadere, barci
surse trimise | ajutor