Fişierul intrare/ieşire:praslea.in, praslea.outSursăONI 2009 - baraj
AutorAdrian AirineiAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.4 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Praslea

Prâslea cel Voinic trebuie să păzească grădina fermecată. El a primit de la Vrăjitorul din Oz o listă cu evenimentele ce urmează să aibă loc în gradină. Mai exact, Vrăjitorul l-a anunţat despre cei N zmei care urmează să se plimbe prin gradină. Fiecare zmeu i va intra în grădină la momentul de timp Ai şi va sta în grădină până în momentul de timp Bi. Pentru a-şi dezvolta forţa de luptător, Prâslea Cel Voinic poate alege la orice moment de timp întreg un grup de zmei (dintre cei care se află în acel moment de timp în gradină) care urmează să-i fie adversari într-o luptă dreaptă, dar atât de scurtă încât durata ei se poate neglija. În această luptă, Prâslea se luptă cu toţi zmeii din grup deodată. Pentru fiecare zmeu i, Prâslea cunoaşte forţa Fi pe care o va acumula dacă se va lupta cu el. De asemenea pentru fiecare zmeu i cunoaşte gradul de risc de a fi „accidentat”, Ri, pe care îl presupune lupta cu acesta. Forţa totală pe care o acumulează Prâslea într-o luptă este suma forţelor acumulate de la fiecare zmeu din grupul ales, iar gradul total de risc pe care şi-l asumă este egal cu suma gradelor de risc ale fiecărui zmeu din grup. Fiind un tânăr cumpătat, Prâslea nu vrea să-şi asume vreodată un grad de risc total strict mai mare decat Rmax.

Cerinta

Să se scrie un program care determină pentru Prâslea Cel Voinic care este forţa totală maximă pe care o poate acumula alegând într-un mod favorabil grupurile de zmei care îi vor fi adversari în luptă.

Date de intrare

Fişierul de intrare praslea.in va conţine pe prima linie numerele N si Rmax. Următoarele N linii vor conţine informaţiile despre zmei adunate de Vrăjitorul din Oz. Linia i+1 va conţine patru numere naturale separate printr-un singur spaţiu, Ai Bi Fi şi Ri, reprezentând informaţiile referitoare la zmeul i.

Date de ieşire

Fişierul de ieşire praslea.out va conţine pe prima linie forţa totală maximă pe care o poate acumula Prâslea Cel Voinic.

Restricţii

  • 1N, Rmax, Fi, Ri512
  • 1AiBi2.000.000.000
  • Toate numerele din fişierul de intrare sunt naturale. În orice moment de timp Prâslea Cel Voinic poate alege doar un singur grup de zmei pe care îi va înfrunta în luptă
  • Prâslea poate lupta cu zmeul i care intră în grădina la momentul Ai şi iese la momentul Bi inclusiv în momentele Ai şi Bi.
  • Oricare zmeu poate fi „invitat” la luptă de mai multe ori pe parcursul perioadei în care stă în grădină.

Exemplu

praslea.inpraslea.out
2 2
1 2 2 1
2 3 2 1
8

Explicaţie

La momentul de timp 1 Prâslea se va lupta cu primul zmeu, acumulând o forta de valoare 2. In momentul de timp 2 se va lupta cu ambii zmei şi va acumula o forţă totală de valoare 4. În momentul de timp 3 se va lupta cu al doilea zmeu, acumulând o forţă de valoare 2. În total, 2 + 4 + 2 = 8.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content