RoAlgo Contest #7 | suxumetre

This was the problem page during the contest. Access the current page here.
Time limit: 1.5s
Memory limit: 256MB
Input:
Output:

"ok, enunturile la muxusetre si 3secv sunt gata, ma ocup FR ACUM de testele la joingraf."

Pentru un șir AA de NN numere definim greutatea acestuia greutate(A)=ijNsp(i,j)greutate(A) = \displaystyle \sum_{i \leq j}^{N} sp(i,j), unde sp(i,j)=(k=ijA[k])modMsp(i,j) = \left( \displaystyle \sum_{k = i}^{j} A[k] \right) \mod M

Sux primește un vector AA de NN elemente în dar de la bunicul său. Acesta într-o zi pleacă în excursie la munte cu cei K1K−1 prieteni ai lui, și fiind foarte atașat de cadoul primit, decide să ia șirul cu el. Ajunși la poalele muntelui , observă cu tristețe că el nu poate să care singur șirul până în vârful muntelui, deoarece este prea greu. Așadar, Sux, încearcă să împartă șirul în KK secvențe disjuncte și nevide astfel încât fiecare din cei K1K − 1 prieteni să primească exact o secvență (rămânându-i lui Sux exact una) și suma greutaților cumulate să fie minimă.

Cerință

Ajutați-l pe Sux să calculeze valoarea minimă.

Date de intrare

Pe prima linie se găsesc trei numere întregi, NN, KK și MM.
Pe a doua linie se află NN numere separate prin cate un spațiu.

Date de ieșire

Pe prima linie se va găsi un număr reprezentând raspunsul problemei.

Restricții și precizări

  • Dacă Sux împarte vectorul în KK secvențe : A1,A2,A3,...,AkA_1, A_2, A_3, ... , A_k, atunci greutatea cumulată este i=1Kgreutate(Ai)\displaystyle \sum_{i=1}^{K} greutate(A_i).
  • Legenda spune că nici până acum nu sunt gata testele la joingraf.
# Scor Restricții
1 10 N10,K10,M10N \leq 10, K \leq 10, M \leq 10
2 30 N100,K100,M30N \leq 100, K \leq 100, M \leq 30
3 10 N1500,K100,M2N \leq 1500, K \leq 100, M \leq 2
4 50 N5000,KN,M30N \leq 5000, K \leq N, M \leq 30

Exemplul 1

stdin

6 2 9
2 6 7 1 8 7 

stdout

62

Explicație

Dacă alegem să împărțim vectorul în secvențele (1,2)(1, 2) și (3,4,5,6)(3, 4, 5, 6) atunci greutatea totală va fi sp(1,1)+sp(2,2)+sp(1,2)+sp(3,3)+sp(4,4)+...+sp(3,6)=72sp(1,1) + sp(2,2) + sp(1,2) + sp(3,3) + sp(4,4) + ... + sp(3,6) = 72
Însa dacă împarțim vectorul în secvențele (1,2,3)(1, 2, 3) și (4,5,6)(4, 5, 6) obținem greutatea totală 6262.

Exemplul 2

stdin

10 5 6
57258 79818 45081 80878 97780 67843 78314 38965 34431 9159 

stdout

30

Contest info

Official contest

Start time: 1699171200000

Total duration: 4h0m0s

Status: Ended

Log in or sign up to be able to send submissions!