Fişierul intrare/ieşire:kc.in, kc.outSursăLot Măgurele 2016 - Baraj 5 Seniori
AutorAndrei HeidelbacherAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test1.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.inkc.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?