MinMaxDivision

#include <algorithm>
#include <numeric>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int blockCount(int max, vector<int> &A) {
    int current = 0;
    int count = 1;
    
    for (int x : A) {
        if (current + x > max) {
            current = x;
            count++;
        } else {
            current += x;
        }
    }
    return count;
}

int solution(int K, int M, vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    
    int lower_bound = *std::max_element(A.begin(), A.end());
    int upper_bound = std::accumulate(A.begin(), A.end(), 0);
    
    if (K == 1) return upper_bound;
    if (K >= A.size()) return lower_bound;
    
    int smallestSum = 0;
    while (lower_bound <= upper_bound) {
        int mid = (upper_bound + lower_bound) / 2;
        int numberOfBlock = blockCount(mid, A);
        
        if (numberOfBlock > K) {
            lower_bound = mid + 1;
        } else if (numberOfBlock <= K) {
            smallestSum = mid;
            upper_bound = mid - 1;
        }
    }
    return smallestSum;
}