Gasto Mensual.


Submit solution

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

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Python, Swift, VB

El Granjero Juan es un mago asombroso para la contabilidad y se ha dado cuenta que podría quedarse sin dinero para manejar la granja. El ya ha calculado y registrado la cantidad exacta de dinero (1 \leq dinero_i \leq 10,000) que él siempre necesitará cada día en los siguientes N (1 \leq N \leq 
10^5) días.

GJ quiere crear un presupuesto para un conjunto secuencial de exactamente M (1 \leq M \leq N) períodos fiscales llamados "fajomeses". Cada uno de estos fajomeses contiene un conjunto de 1 ó más días consecutivos. Cada día está contenido en exactamente un fajomes.

El objetivo de GJ es organizar los fajomeses de tal manera de minimizar los gastos del fajomes con el mayor gasto y por lo tanto determinar su límite de gasto mensual.

Entrada

  • Línea 1: Dos enteros separados por un espacio: N y M

  • Líneas 2..N+1: La línea i+1 contiene el número de dólares que el Granjero Juan gasta en el día i-ésimo.

Ejemplo de Entrada

7 5
100
400
300
100
500
101
400

Detalles de la Entrada: Hay 7 días para distribuir a través de 5 fajomeses. El gasta $100, $400, $300, $100, $500, $101 y $400 en días consecutivos.

Salida

En una sola menor limite mensual posible que el Granjero Juan debe tener para sobrevivir.

Ejemplo de Salida

500

Detalles de la Salida: Si el Granjero Juan programa los meses de tal manera que los dos primeros días son un mes, el tercero y el cuarto son un mes, y los últimos tres sean sus propios meses, él gasta a lo más $500 en cada mes. Cualquier otro método de programación da un limite de mínimo mensual más grande.

100 400   300 100   500   101   400   Gasto Diario
---1---   ---2---   -3-   -4-   -5-   Número de Mes
  500       400     500   101   400   Gasto Mensual

Comments

There are no comments at the moment.