Rezolvare PBinfo #4430

Costel deține un șir p de n pietricele prețioase numerotate de la 1 la n. Deoarece Costel este un om superstițios, el colecționează pietricele doar de anumite tipuri. Tipul unei pietricele este reprezentat de o literă mică a alfabetului englez, iar fiecare tip în parte are o anumită valoare. Într-o zi, Costel s-a decis să distribuie șirul de n pietricele pe k rafturi astfel încât fiecare raft să conțină câte o subsecvență nevidă de pietricele din șirul original, iar la final, fiecare pietricică să se afle pe exact un raft. Definim valoarea unui raft ca fiind suma valorilor pietricelelor de pe acel raft.

Cerința

Fiind dat șirul de n pietricele, să se distribuie pietricelele din șir în k subsecvențe disjuncte astfel încât:
1) Cea mai mare valoare a unui raft să fie maximă.
2) Cea mai mică valoare a unui raft să fie maximă.

Date de intrare

Fișierul de intrare pietricele.in conține pe prima linie numerele naturale c, n și k separate prin câte un spațiu, unde c reprezintă cerința care trebuie rezolvată, n reprezintă numărul de pietricele din șir, iar k reprezintă numărul de rafturi pe care vor fi distribuite pietricelele. Cea de-a doua linie a fișierul va conține n litere mici ale alfabetului englez, reprezentând tipurile pietricelelor din șirul deținut de Costel. Cea de-a treia linie conține 26 de numere separate prin câte un spațiu, reprezentând valoarea fiecărui tip de pietricică de la a la z.

Date de ieșire

Fișierul de ieșire pietricele.out va conține răspunsul pentru cerința dată.

Restricții și precizări

• c ∈ {1, 2}
• 1 ≤ k ≤ n ≤ 200.000
• valorile tipurilor de pietricele sunt cuprinse în intervalul [1, 2.000.000.000].
• o subsecvenţă a șirului p este o succesiune de pietricele aflate pe poziții consecutive: p[i], p[i+1], …, p[j], 1 ≤ i ≤ j ≤ n.
• două subsecvențe sunt disjuncte dacă nu au nicio pietricică în comun.
• se recomandă folosirea tipului de date long long.
• Pentru 10 puncte, c = 1 și pentru fiecare pietricică din șir, valoare[p[i]] ≤ valoare[p[i+1]]
• Pentru 20 puncte, c = 1, fără restricții suplimentare.
• Pentru 10 puncte, c = 2, n ≤ 5000 și k = 3.
• Pentru 10 puncte, c = 2 și 1 ≤ k ≤ n ≤ 100
• Pentru 10 puncte, c = 2 și valorile tuturor tipurilor de pietricele sunt egale.
• Pentru 40 puncte, fără restricții suplimentare.

Exemplul 1:

pietricele.in

1 12 3
abbaacabcbaa
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

pietricele.out

18

Explicație

Cea mai mare valoare pe care o poate avea un raft este 18 și se obține prin următoarea distribuire pe rafturi: a, bbaacabcba, a, fiecare cu valorile 1, 18, respectiv 1.

Exemplul 2:

pietricele.in

2 12 3
aabaacabcbaa
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

pietricele.out

6

Explicație

Șirul se distribuie pe 3 rafturi astfel: aabaa, cab, cbaa, fiecare cu valorile 6, 6 respectiv 7. Astfel, 6 este cea mai mică valoare a unui raft, care pentru acest exemplu este maximul posibil.