#include <bits/stdc++.h>
using namespace std;

// Function to count the number of painters required to paint all boards in "time"
int countPainters(vector<int> &boards, int time) {
    int n = boards.size(); // Size of the array
    int painters = 1;      // Start with 1 painter
    long long boardsPainter = 0;
    
    for (int i = 0; i < n; i++) {
        if (boardsPainter + boards[i] <= time) {
            // Allocate board to the current painter
            boardsPainter += boards[i];
        } else {
            // Allocate board to the next painter
            painters++;
            boardsPainter = boards[i];
        }
    }
    
    return painters;
}

// Function to find the largest minimum distance
int findLargestMinDistance(vector<int> &boards, int k) {
    // Find the search space for binary search
    int low = *max_element(boards.begin(), boards.end());
    int high = accumulate(boards.begin(), boards.end(), 0);
    
    // Apply binary search:
    while (low <= high) {
        int mid = (low + high) / 2;
        int painters = countPainters(boards, mid);
        
        if (painters > k) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    return low; // Minimum possible maximum time
}

int main() {
    vector<int> boards = {10, 20, 30, 40};
    int k = 2; // Number of painters
    
    int ans = findLargestMinDistance(boards, k);
    cout << "The answer is: " << ans << "\n";
    
    return 0;
}