== include(page="template/taskheader" task_id="ksecv2") ==
Poveste şi cerinţă...
Dupa ce s-a plictisit de condus in 'Viteza':problema/viteza Mirel s-a dus la supermarket sa-si faca cumparaturile. Pierzand mult timp cu masina prin oras s-a trezit ca are nevoie de foarte multe produse de la supermarket si ca are la el doar $K$ sacose(supermarketul la care merge Mirel deobicei nu vinde sacose). Acolo isi alege produsele, se duce cu ele le casa si le laza vanzatoarei ca sa i se faca nota de plata. Se duce apoi spre capat sa puna obiectele in sacose in ordinea care vin. Fiecare obiect pe care l-a cumparat are o fragilitate care poate fi notata cu un numar intreg, cu cat e mai mare numarul cu atat e mai fragil obiectul.
Sacosele de care dispune sunt enorm de mari ele putand tine oricate obiecte cumparate insa acestea trebuie puse unele peste altele. insa din pacate daca peste un obiect se pune unul mai putin fragil acesta se sparge. Mirel isi da seama ca din aceasta cauza nu poate lua cu el toate produsele pe care le-a adus la casa si neavand rabdare el foloseste o strategie simpla. Pentru fiecare obiect care vine el actioneaza astfel:
* 1) Daca vrea poate sa-i spuna vanzatoarei ca va veni mai tarziu pentru el
* 2) Daca il poate pune in ultima sacosa peste celelalte fara sa sparga nimic atunci asa face
* 3) Doar daca nu poate sa il puna in ultima sacosa, pune sacosa deoparte si ia una noua in care pune doar acest obiect.
El vrea sa ia acasa cat mai multe din produsele alese asa ca va roaga pe voi sa-i spuneti care e numarul maxim se produse pe care le poate pastra, pentru restul fiind nevoit sa se intoarca mai tarziu. Daca insa el nu poate umple toate cele K sacose folosind strategia sa atunci se va intoarce in magazin sa mai aleaga produse.
h2. Date de intrare
Fişierul de intrare $ksecv2.in$ ...
Fişierul de intrare $ksecv2.in$ contine pe prima linie $N$ si $K$ reprezentand numarul de produse, respctiv numarul de sacose de care dispune Mirel.
Urmatoarea linie contine $N$ numere intregi reprezentand fragilitatea obiectelor in ordinea in care vin spre Mirel.
h2. Date de ieşire
În fişierul de ieşire $ksecv2.out$ ...
În fişierul de ieşire $ksecv2.out$ trebuie sa se gaseasca un singur numar natural reprezentand numarul maxim de produse pe care le poate lua cu cele $K$ sacose folosind strategia descrisa sau $-1$ daca nu poate umple cele $K$ plase cu strategia aleasa.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 3000$
* $1 ≤ K ≤ 500$
* $-1.000.000.000 ≤ fragilitatea unui produs ≤ 1.000.000.000$
* $Pentru 40% din teste 1 ≤ N ≤ 500 si 1≤ K ≤ 100$
* $Pentru inca 30% din teste 1 ≤ N ≤ 2000 si 1 ≤ K ≤ 200$
h2. Exemplu
table(example). |_. ksecv2.in |_. ksecv2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|5 3
10 10 4 0 -8
|4 |
|3 2
1 2 3
|-1|
h3. Explicaţie
...
Pentru primul exemplu:
Mirel poate pastra produsele cu indicii ({$1$}, {$2$}), ({$3$}) si ({$5$}) sau ({$1$}, {$2$}), ({$3$}) si ({$4$}) (Prin paranteze am marcat felul in care pune Mirel produsele in plase)
Pentru al doilea exemplu:
Oricum ar lua Mirel o parte in produse el poate umple maxim o plasa dupa strategia lui si deci se va intoarce inapoi sa mai aleaga produse.
== include(page="template/taskfooter" task_id="ksecv2") ==
== include(page="template/taskfooter" task_id="ksecv2") ==
