| Fişierul intrare/ieşire: | kc.in, kc.out | Sursă | Lot Măgurele 2016 - Baraj 5 Seniori |
| Autor | Andrei Heidelbacher | Adăugată de |  Heidelbacher Andrei •a_h1926 |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
KC
Tassadar a supravieţuit cursului de Kultură şi Civilizaţie, dar a rămas profund afectat de această experienţă şi este convins că, de fapt, cursurile erau incoerente.
Pentru a verifica acest lucru, el a întocmit un dicţionar care cuprinde toate cuvintele incoerente pe care le-a întâlnit de-a lungul vieţii. Gradul de incoerenţă al unui cuvânt din dicţionar este egal cu lungimea cuvântului. Cursul de Kultură şi Civilizaţie poate fi reprezentat printr-un şir de N litere mici ale alfabetului latin.
Tassadar vrea să insereze spaţii în curs şi să delimiteze, astfel, cuvintele care apar în acesta. El doreşte să facă acest lucru astfel încât suma gradelor de incoerenţă ale cuvintelor din curs să fie maximă.
Ajutaţi-l pe Tassadar să afle cât de incoerent este cursul de Kultură şi Civilizaţie!
Date de intrare
Fişierul de intrare kc.in conţine pe prima linie numerele N şi K, reprezentând lungimea cursului, respectiv numărul de cuvinte din dicţionar. Pe următoarea linie se află un şir de N litere, reprezentând cursul de Kultură şi Civilizaţie. Pe următoarele K linii se vor afla cuvintele din dicţionar, câte unul pe linie.
Date de ieşire
Fişierul de ieşire kc.out va conţine pe prima linie suma maximă a gradelor de incoerenţă care se poate obţine prin delimitarea cuvintelor din curs cu spaţii.
Restricţii
- 1 ≤ N ≤ 100 000
- 1 ≤ K ≤ 100 000
- 1 ≤ L ≤ 100 000, unde L este suma lungimilor cuvintelor din dicţionar
- Un cuvânt este o subsecvenţă maximală de litere mici ale alfabetului latin şi este delimitat la stânga şi la dreapta fie de un spaţiu, fie de începutul cursului, fie de sfârşitul cursului
- Dacă un cuvânt din curs nu apare în dicţionar, acesta are gradul de incoerenţă 0
- Pentru teste în valoare de 10 puncte, N ≤ 1000 şi L ≤ 1000
- Pentru teste în valoare de alte 30 de puncte, N ≤ 1000
Exemplu
| kc.in | kc.out |
|---|---|
| 3 3 abc a c abc | 3 |
Explicaţie
Există patru moduri în care putem delimita cuvintele din curs cu spaţii: "abc" (conţine un singur cuvânt cu gradul de incoerenţă 3), "ab c" (conţine un cuvânt cu gradul de incoerenţă 0 şi unul cu gradul de incoerenţă 1), "a bc" (conţine un cuvânt cu gradul de incoerenţă 1 şi unul cu gradul de incoerenţă 0) şi "a b c" (conţine două cuvinte cu gradul de incoerenţă 1 şi unul cu gradul de incoerenţă 0). Dintre toate aceste modalităţi, este optim să nu inserăm niciun spaţiu în curs, pentru a obţine suma gradelor de incoerenţă maximă, aceasta fiind egală cu 3.
