Algorithm

First, we will find the maximum element and the summation of the given array.
We will use a loop(say time) to check all possible answers from max(arr[]) to sum(arr[]).
Next, inside the loop, we will send ‘time’, to the function countPainters() function to get the number of painters to whom we can allocate the boards.
The first value of ‘time’, for which the number of painters will be lesser or equal to ‘k’, will be our answer. So, we will return that particular value of ‘time’.
Finally, if we are out of the loop, we will return max(arr[]) as there cannot exist any answer smaller than that.

Code

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

// Class to solve the Painter Partition Problem
class PainterPartition {
public:
    // Helper function to count how many painters are required to paint the boards within the given time limit
    int countPainters(vector<int> &boards, int time) {
        int n = boards.size();
        int painters = 1; // Start with one painter
        long long boardsPainter = 0; // Current total board length assigned to a painter

        for (int i = 0; i <