Serpientes.

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C, C++, Pascal, Python

De acuerdo a la leyenda, San Patricio terminó con todas las culebras en Mooland hace más de mil años. sin embargo, desde ese tiempo las culebras volvieron a Mooland. El día de San Patricio era el 17 de Marzo, por lo tanto Bessie va a conmemorar San Patricio terminado con todas las culebras de Mooland de una vez por todas.

Bessie está equipada con una red para capturar culebras distribuidas en \(N\) grupos en una recta \((1 \leq N \leq 400)\). Bessie debe capturar cada culebra en cada grupo en el orden en que los grupos aparezcan en la recta. Cada vez que Bessie captura un grupo, ella puede poner a las culebras en una jaula y comenzar con una red vacía para el siguiente grupo.

Una red de tamaño \(a\) implica que Bessie puede capturar cualquier grupo conteniendo \(g\) culebras, donde \(g≤s\). Sin embargo, cada vez que Bessie captura un grupo de culebras de tamaño \(g\) con una red de tamaño a, ella gasta \(a−g\) espacio. La red de Bessie puede comenzar en cualquier tamaño y ella puede cambiar el tamaño de su red \(K\) veces \((1 \leq K < N)\).

Por favor digale a Bessie la cantidad mínima de espacio total dspercidiado que puede acumular después de capturar todos los grupos.

Entrada

La primera línea contiene \(N\) y \(K\). La segunda línea contiene \(N\) enteros, \((a_1,…,a_N)\), donde \(a_i\) \((0≤a_i≤10^6)\) es el número de culebras en el grupo i-ésimo.

Salida

Dé como salida un entero dando la cantidad mínima de espacio desperdiciado después que Bessie capture todas las culebras.

Ejemplo de Entrada

6 2
7 9 8 2 3 2

Ejemplo de Salida

3

La red de Bessie comienza con un tamaño de \(7\). Después que ella captura el primer grupo de culebras, ellas cambia su red a un tamaño de \(9\) y mantiene ese tamaño hasta el cuarto grupo de culebras cuando ella cambia su red a tamaño \(3\). El espacio desperciado total es \((7−7)+(9−9)+(9−8)+(3−2)+(3−3)+(3−2)=3\).


Comments


  • 0
    PedroPabloAB  commented on April 1, 2021, 8:45 p.m.

    I don't know


  • 0
    Osnielfc_07  commented on April 1, 2021, 5:45 p.m.

    Una pregunta : Si yo tiro una matriz : // dp[maxn][maxn][maxn] // cual puede ser el mayor valor de maxn.


    • 0
      aniervs  commented on April 1, 2021, 8:49 p.m. edited

      Si dp[i][j][k] consume \(B\) bytes, entonces \(\frac{\text{maxn}^3 \cdot B}{10^6} \le \text{AvailableMemoryInMegaBytes}\); es decir: \(\text{maxn} \le \sqrt[3]{\frac{\text{AvailableMemoryInMegaBytes}\cdot 10^6}{B}}\). Para este problema: \(\text{maxn} \le 200\).


  • 0
    PedroPabloAB  commented on March 30, 2021, 8:55 p.m.

    Chulo y algo complejo


  • 0
    Osnielfc_07  commented on March 30, 2021, 12:48 a.m.

    Esta chulo el problema este.