| Fişierul intrare/ieşire: | ksecv2.in, ksecv2.out | Sursă | Algoritmiada 2012, Runda finala |
| Autor | Adrian Diaconu | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Ksecv2
Dupa ce s-a plictisit de condus in Viteza2 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 lasa vanzatoarei ca sa i se faca nota de plata. Se duce apoi spre capat sa puna obiectele in sacose in ordinea in 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 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.
Date de intrare
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.
Date de ieşire
Î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.
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
Exemplu
| ksecv2.in | ksecv2.out |
|---|---|
| 5 3 10 10 4 0 -8 | 4 |
| 3 2 1 2 3 | -1 |
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.
