O problema gira em torno da otimização de um orçamento agrícola, onde o objetivo é minimizar o gasto máximo em qualquer período fiscal, conhecido como "fajomês". Temos um total de N dias com desepsas diárias específicas e precisamos dividir esses dias em exatamente M fajomêses consecutivos. Cada dia deve pertencer a um único fajomês.

Entrada

A primeira linha contém dois inteiros separados por espaço: N (número de dias) e M (número de períodos fiscais).

As linhas subsequentes (de 2 a N+1) contêm o valor gasto em cada dia, onde o valor na linha i+1 corresponde ao gasto do i-ésimo dia.

Saída

Imprima um único inteiro: o menor valor máximo de gasto mensal que o fazendeiro pode suportar.

Exemplo de Entrada

7 5
100
400
300
100
500
101
400

Exemplo de Saída

500

Dica

Se os meses forem organizados de forma que os dois primeiros dias formem um mês, os dois dias seguintes formem outro mês, e os últimos três dias formem seus próprios meses, o gasto máximo em qualquer mês será de $500. Qualquer outra divisão resultará em um limite de gastos mensais maior.

Implementação

Este problema pode ser eficientemente resolvido utilizando busca binária. A ideia é que, se for possível dividir os N dias em M fajomêses com um gasto máximo de X por mês, então também é possível com qualquer limite superior a X. Isso nos permite buscar o menor X possível.

A função de verificação (verificaCapacidade ou C no código) determinará se é viável dividir os dias em M fajomêses, garantindo que o gasto total de cada fajomês não exceda um limite limiteMaximo.

O limite inferior para a busca binária será o maior gasto diário individual (já que um dia sozinho não pode exceder o limite mensal) e o limite superior será a soma de todos os gastos diários (o caso em que há apenas um fajomês).

Código de Exemplo (C++)

A lógica principal envolve uma função que verifica se um determinado limiteMaximo é alcançável. Esta função itera pelos gastos diários, acumulando o gasto em um fajomês atual. Se a adição de um novo dia exceder o limiteMaximo, um novo fajomês é iniciado com o gasto desse dia. Se o número de fajomêses necessários for menor ou igual a M, o limiteMaximo é viável.

Versão Otimizada do Código de Verificação

A versão AC (Acepted) inclui uma verificação crucial no início da função de verificação: se qualquer gasto diário individual for maior que o limiteMaximo proposto, é impossível atender a esse limite, e a função retorna false imediatamente. Isso evita a necessidade de inicializar o limite inferior da busca binária com o maior gasto diário, permitindo que ele comece em 0.

#include <cstdio>
#include <algorithm> // Necessário para std::max

// Define um limite superior razoável para o número de dias
const int MAX_DIAS = 1e5 + 5;
int gastosDiarios[MAX_DIAS];
int numDias, numPeriodos;

// Função para verificar se é possível dividir os dias em 'numPeriodos'
// com um gasto máximo de 'limiteMaximo' por período.
bool podeDividir(int limiteMaximo) {
    int gastoAtual = 0;
    int periodosUsados = 0;

    for (int i = 0; i < numDias; ++i) {
        // Se um único dia excede o limite, este limite não é viável.
        if (gastosDiarios[i] > limiteMaximo) {
            return false;
        }

        // Se adicionar o gasto do dia atual exceder o limite máximo,
        // inicia um novo período fiscal.
        if (gastoAtual + gastosDiarios[i] > limiteMaximo) {
            periodosUsados++;
            gastoAtual = gastosDiarios[i];
        } else {
            // Caso contrário, adiciona o gasto ao período atual.
            gastoAtual += gastosDiarios[i];
        }
    }

    // Incrementa o contador de períodos, pois o último período também conta.
    // Se a lógica anterior adicionou um novo período, ele já foi contado.
    // Se não, significa que estamos dentro do último período e precisamos contar ele.
    // A forma mais simples é sempre incrementar no final.
    periodosUsados++;

    // Retorna true se o número de períodos usados for menor ou igual ao permitido.
    return periodosUsados <= numPeriodos;
}

int main() {
    scanf("%d %d", &numDias, &numPeriodos);

    int somaTotalGastos = 0;
    for (int i = 0; i < numDias; ++i) {
        scanf("%d", &gastosDiarios[i]);
        somaTotalGastos += gastosDiarios[i];
    }

    // Define os limites para a busca binária.
    // O limite inferior pode ser 0, pois a função 'podeDividir' trata
    // casos onde um gasto diário excede o limite.
    int limiteInferior = 0;
    // O limite superior é a soma total dos gastos, representando o caso de um único período.
    int limiteSuperior = somaTotalGastos;
    int melhorLimite = somaTotalGastos;

    // Executa a busca binária para encontrar o menor limite máximo viável.
    while (limiteInferior <= limiteSuperior) {
        int meio = limiteInferior + (limiteSuperior - limiteInferior) / 2;
        if (podeDividir(meio)) {
            // Se for possível com 'meio', tentamos um limite menor.
            melhorLimite = meio;
            limiteSuperior = meio - 1;
        } else {
            // Se não for possível, precisamos de um limite maior.
            limiteInferior = meio + 1;
        }
    }

    printf("%d\n", melhorLimite);

    return 0;
}
</algorithm></cstdio>