Les secrets de la célèbre prison Habs Qara à Meknès - Programmation compétitive

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <climits>

using namespace std;

bool faisable(const vector<int> &pages, int n, int m, int min_actuel) {
    int besoin_chercheurs = 1;
    int somme_actuelle = 0;

    for (int i = 0; i < n; i++) {
        // Si un livre dépasse déjà la limite, impossible
        if (pages[i] > min_actuel)
            return false;

        // Si l'ajout du livre dépasse la limite, on passe au chercheur suivant
        if (somme_actuelle + pages[i] > min_actuel) {
            besoin_chercheurs++;
            somme_actuelle = pages[i];

            // Si on a besoin de plus de chercheurs que disponible
            if (besoin_chercheurs > m)
                return false;
        } else {
            somme_actuelle += pages[i];
        }
    }
    return true;
}

int solution(vector<int> pages, int n, int m) {
    // Retourner -1 si le nombre de livres est inférieur au nombre de chercheurs
    if (n < m)
        return -1;
    
    // Trier les pages (optionnel)
    sort(pages.begin(), pages.end());
    
    // Calculer la somme des pages
    long long somme = accumulate(pages.begin(), pages.end(), 0);

    int debut = 0;
    int fin = somme;
    int maxpages = INT_MAX;

    // Recherche binaire
    while (debut <= fin) {
        int milieu = (debut + fin) / 2;
        if (faisable(pages, n, m, milieu)) {
            maxpages = milieu;
            fin = milieu - 1;
        } else {
            debut = milieu + 1;
        }
    }
    return maxpages;
}

int main() {
    int n, m, val;
    cin >> n >> m;
    vector<int> pages;
    for (int i = 0; i < n; i++) {
        cin >> val;
        pages.push_back(val);
    }

    cout << solution(pages, n, m) << endl;
    
    return 0;
}