Cacher is the code snippet organizer for pro developers

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

// Given an array, partition it into k continuous segments so that
// the maximum sum among the individual partitions should be minimum.
// Input format:
// 1
// 9
// 10 20 30 40 50 60 70 80 90
// 3
// 9
// 1 4 2 10 23 3 1 0 20
// 3
// Output:
// 170
// 24
bool check(vector<int> arr, int minSum,int k){
    // sum of groups must be >=minSum
    // check if we can form exactly k goups with each having group sum>=minSum
    int partCount=0;
    int tempSum=0;
    int i=0;
    while(i<arr.size()){
        tempSum+=arr[i];
        if(i==arr.size()-1 || tempSum>=minSum){
            tempSum=0;
            partCount++;
            if(partCount>k){
                return false;
            }
        }
        i++;
    }
    if(partCount<k){
        return false;
    }else{
        return true;
    }
}
int calcMax(vector<int> arr, int minSum){
    // we know that we can form k groups with this given minSum
    // find the maxSum possible in these groupings
    int tempSum=0;
    int maxSum=INT_MIN;
    for(int i=0;i<arr.size();i++){
        tempSum+=arr[i];
        if(i==arr.size()-1 || tempSum>=minSum){
            if(tempSum>maxSum){
                maxSum=tempSum;
            }
            tempSum=0;
        }
    }
    return maxSum;
}
int smallestMaxSum(vector<int> arr, int k){
    if(k>arr.size()){
        return -1; // not possible
    }
    int arrSum=0;
    for(int i=0;i<arr.size();i++){
        arrSum+=arr[i];
    }
    if(arrSum==0){
        return 0;
    }
    int start=0,end=arrSum;
    // let x be the least sum to form a group
    // bin search for this least sum to form k groups
    while(start<end){
        if(start==end-1){
            if(check(arr,start,k)==true){
                return calcMax(arr,start);
            }else{
                return calcMax(arr,end);
            }
        }
        int mid=start+(end-start)/2;
        cout<<start<<" "<<mid<<" "<<end<<endl;
        if(check(arr,mid,k)==true && check(arr,start,k)!=true){
            start=mid; // if we have solution at mid and not at left, search right
        }else{
            end=mid; // if we dont have solution at mid, search left
        }
    }
}

int main(){
    // freopen("ip.txt","r",stdin);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int> arr(n);
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        int k;
        cin>>k;
        cout<<smallestMaxSum(arr,k)<<endl;
    }
    return 0;
}