Între timp, într-un univers paralel…
Ștefan Ghe este creatorul site-ului renumit de probleme de algoritmică InfoZona. Din păcate, verișorul său diabolic, Feștan Ț, punându-și în practică skill-urile de hacker nebunatic, a spart site-ul InfoZona și îl va da înapoi domnului Ștefan doar dacă reușeste să rezolve următoarea problemă:
Cerința
Se dă un șir A
, indexat de la 1
, de N
numere naturale nenule, reprezentând un raft de sandale. Vom defini funcția \( F(l,r) = ( \sum_{i=l}^{r} A[i] )^3 \) ca fiind costul pentru a cumpara sandalele din secvența [l, r]
laolaltă, toate în același coș de cumpărături. Feștan Ț are K
coșuri de cumpărături la dispoziție și dorește să afle care este prețul minim pe care poate cumpăra toate cele N
sandale, folosind coșurile de cumpărături de care dispune.
Ajutați-l pe domnul Ștefan Ghe să-și recupereze site-ul rezolvând această problemă și vă va face cinste cu o bere și cinci cămile!
Formatul input-ului
N K A1 A2 ... AN
Formatul output-ului
R
Restricții și precizări
1 ≤ N ≤ 5000
1 ≤ K ≤ N
1 ≤ A[i] ≤ 30
- Se garantează că răspunsul poate fi reprezentat pe
64
de biți cu semn
Exemplu 1:
Intrare
6 1 1 5 4 2 6 8
Ieșire
17576
Explicație
Deoarece K = 1
, Feștan Ț este obligat sa cumpere toate sandalele laolalta. \( (1+5+4+2+6+8)^3 = 17576 \)
Exemplu 2:
Intrare
6 3 1 5 4 2 6 8
Ieșire
2024
Explicație
Feștan Ț va folosi toate cele K = 3
cosuri de cumparaturi pentru a cumpara sandalele din secvențele [1, 3]
, [4, 5]
și [6]
. \( (1+5+4)^3 + (2+6)^3 + 8^3 = 2024 \)