H - Hai cu Crackul

Time limit: 2s Memory limit: 64MB Input: Output:

Cerință

Avem la dispozitie un șir vv de NN numere, un KK și un CC.

Se aleg maxim KK subsecvențe continue disjuncte. Care este suma costurilor subsecvențelor maximă?
Costul secvenței [ij]=(v[i]+v[j])2+C+p=ijv[p][i \dots j] = (v[i]+v[j])^2+C+\sum_{p=i}^{j}v[p], i<ji < j.

Date de intrare

Pe prima linie se găsesc numerele NN, KK și CC.
Pe a doua linie este șirul vv de NN numere.

Date de ieșire

Suma costurilor maximă posibilă.

Restricții și precizări

  • 1N1051 \leq N \leq 10^5;
  • 1KN21 \leq K \leq \left \lfloor{\frac{N}{2}}\right \rfloor ;
  • 1vi,C1041 \leq v_i, C \leq 10^4;
  • Fiecare subsecvență aleasă trebuie să aibă cel puțin 22 elemente.

Exemplul 1

stdin

5 2 1
2 3 1 2 1

stdout

44

Explicație

Alegem subsecvențele [1,2][1,2] și [4,5][4,5], costurile de (2+3)2+1+2+3=31(2+3)^2+1+2+3=31 și (2+1)2+1+2+1=13(2+1)^2+1+2+1=13, în total 4444.

Exemplul 2

stdin

10 4 6
5 7 31 8 3 19 48 6 9 5

stdout

6764

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