| Fişierul intrare/ieşire: | gordonramsay.in, gordonramsay.out | Sursă | Junior Challenge 2018 |
| Autor | Tinca Matei | Adăugată de |  Junior Challenge •JuniorChallenge2018 |
| Timp execuţie pe test | 1 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Gordon Ramsay
După rezultatele recente, Semicerc a intrat în pământ de ruşine... aşa că s-a decis să îşi deschidă un restaurant împreună cu Giotozila care strânge bani pentru un coş de gunoi mai rezistent.
Ca orice bişniţă afacere, să deţii un restaurant nu este uşor. Trebuie să ai grijă ca ingredientele să fie mereu prezente în frigidere ca să poţi satisface cât mai mulţi clienţi (implicit să faci cât mai mulţi bani). De asemenea, trebuie să ai grijă ca ingredientele să fie mereu proaspete ca să nu fi responsabil pentru toxinfecţii alimentare sau alte boli.
În această lume fictivă, ziua durează N ore şi în fiecare oră vine un client căruia îi cunoşti felul de mâncare pe care îl va comanda. Meniul acestui restaurant conţine K feluri de mâncare. Considerăm că fiecare fel de mâncare este alcătuit dintr-un singur ingredient. Fiecare ingredient este definit de cost, profit şi rezistenţă. Costul unui ingredient este suma de bani plătită pentru a cumpăra o unitate dintr-un anumit ingredient, profitul este suma de bani câştigată dacă vinzi felul de mâncare corespunzător unui ingredient, iar rezistenţa reprezintă numărul de ore în care ingredientul este proaspăt.
Pentru procura ingredientelor, restaurantul deţine un blatmobil care vine din t în t secunde începând de la ora 0, deci în momentele 0, t, 2 * t, 3 * t, 4 * t, ..., q * t unde q * t < N. Acesta vine cu ingrediente proaspete de la non-stop, mai exact cu x1 unităţi din primul ingredient, x2 unităţi din al doilea ingredient, ..., xK din al K-ulea ingredient. Astfel, de fiecare dată când vine blatmobilul, patronii trebuie să plătească x1 * cost1 + x2 * cost2 + ... + xK * costK JC (Junior Coins). Din motive sanitare, ingredientele care erau înainte în frigider vor fi aruncate la gunoi.
O zi de lucru funcţionează astfel: la fiecare oră vine un client care comandă un fel de mâncare; dacă în frigider se află ingredientul necesar pentru felul de mâncare, acesta va fi servit cu acel fel de mâncare, va fi fericit şi va lăsa profitfel JC, altfel va pleca nemulţumit şi nu va lăsa niciun JC.
Cerinţa
Scopul vostru este să găsiţi t, x1, x2, ..., xK cu semnificaţia din enunţ astfel încât să obţineţi un profit maxim.
Date de intrare
Fişierul de intrare gordonramsay.in va conţine pe prima linie numerele N şi K reprezentând numărul de ore dintr-o zi, respectiv numărul de feluri din meniu. Pe a doua linie va fi un şir de N numere care reprezintă comenzile fiecărui om. Pe următoarele K linii se vor găsi triplete de numere, a i-a linie, 1 ≤ i ≤ K, conţinând numerele costi, profiti şi rezistenţăi.
Date de ieşire
În fişierul de ieşire gordonramsay.out se vor găsi pe prima linie profitul maxim obţinut, pe a doua linie numărul t cu semnificaţia din enunţ, iar pe a treia linie se vor găsi K numere x1, x2, ..., xK cu semnificaţia din enunţ.
Restricţii
- 1 ≤ costi, profiti, rezistenţăi ≤ 109; 1 ≤ i ≤ N
- Primul client vine la ora 0, al doilea la ora 1, ..., al N-ulea la ora N - 1
- Numerele din output trebuie să fie numere naturale
- 1 ≤ t ≤ N
- 0 ≤ xi ≤ N; 1 ≤ i ≤ K
- Un aliment adus la momentul i poate fi utilizat pentru a satisface orice client care vine la restaurant în momentele din intervalul [i, i + min(t, rezistenţăaliment))
- În caz că există mai multe soluţii care aduc profitul maxim, se poate afişa orice soluţie.
- Subtask Rotten (Dosar penal pentru încălcarea normelor sanitare) - 10 puncte (testele 1-2): N * K ≤ 100
- Subtask Raw (Toxiinfecţie alimentară) - 15 puncte (testele 3-5): N * K ≤ 500, N ≤ 100
- Subtask Burnt (Dezgustător) - 15 puncte (testele 6-8): N * K ≤ 2 * 104, N ≤ 4000
- Subtask Well done (aproape OK, să zicem) - 30 puncte (testele 9-14): N * K ≤ 2 * 10^5
- Subtask Medium rare (Perfect) - 30 puncte (testele 15-20): N * K ≤ 2 * 10^6
Exemplu
| gordonramsay.in | gordonramsay.out |
|---|---|
| 12 3 2 1 1 1 2 1 1 1 2 3 1 1 2 8 5 7 15 11 2 3 2 | 70 4 3 1 0 |
Explicaţie
Blatmobilul aduce provizii de 3 ori (în momentele 0, 4, 8), deci Semicerc şi Giotozila vor plăti 3 * (cost1 * x1 + cost2 * x2 + cost3 * x3) = 3 * (2 * 3 + 7 * 1 + 2 * 0) = 39 JC.
Din primul aliment vom avea 3 bucăţi care vor fi valabile în toate momentele din intervalul [0, 4) (ar fi fost intervalul [0, 5), dar la momentul 4 vine din nou blatmobilul şi se goleşte frigiderul), 3 bucăţi care vor fi valabile în toate momentele din intervalul [4, 8) şi 3 bucăţi care vor fi valabile în toate momentele din intervalul [8, 12). Cu primele 3 bucăţi putem satisface comenzile din momentele 1, 2, 3, cu următoarele 3 bucăţi comenzile 5, 6, 7, iar cu ultimele 3 bucăţi satisfacem comenzile 10, 11, în total 8 comenzi.
Din al doilea aliment vom avea o bucată valabilă în intervalul [0, 4), o bucată valabilă în intervalul [4, 8) si o bucată valabilă în intervalul [8, 12). Cu toate aceste bucăţi satisfacem toate comenzile din momentele 0, 4, 8, în total 3 comenzi.
Profitul total o să fie deci 8 * profit1 + 3 * profit2 + 0 * profit3 - 39 = 8 * 8 + 3 * 15 + 0 - 39 = 70 JC.
Observaţie: dacă am fi avut x3 = 1, am fi avut o bucată valabilă în intervalul [0, 2) (după 2 ore, al treila aliment expiră), o bucată valabilă în intervalul [4, 6) si o bucată valabilă în intervalul [8, 10).
