Maximise the minimum height of the flower | Binary Search | Hard | MUST DO

https://practice.geeksforgeeks.org/problems/899540d741547e2d75d1c5c03a4161ab53affd13/1?page=1&difficulty[]=1&difficulty[]=2&status[]=unsolved&category[]=Dynamic%20Programming&category[]=Binary%20Search&category[]=Trie&category[]=union-find&sortBy=latest

It is also on codeforces

You have a garden with n flowers lined up in a row. The height of ith flower is ai units. You will water them for k days. In one day you can water w continuous flowers (you can do this only once in a single day). Whenever you water a flower its height increases by 1 unit. You need to maximize the height of the smallest flower.

Example 1:

Input:
N=6
K=2
W=3
a[]={2,2,2,2,1,1}
Output:
2
Explanation:
Water last three flowers for two days.The new heights
will be {2,2,2,3,2,2}

Example 2:
Input:
N=2
K=5
W=1
a[]={5,8}
Output:
9
Explanation:
For the first four days water the first flower then
water the last flower once.

Constraints:

1 <= N <= 10^5
1<=w<=N
1<=K<=10^5
1 <= a[i] <= 10^9

---------------------------------------------------------------------------------------------------------------------------------------
class Solution{
    public:
        bool isOK(vector<int> &arr, int days, int cs, long long int h){
            int n=arr.size();

            vector<long long> waterSupply(n,0);

            if(arr[0]<h){
                waterSupply[0]=h-arr[0];
                days-=(h-arr[0]);
            }

            if(days<0){
                return false;
            }

            for(int i=1;i<arr.size();i++){
                waterSupply[i]=waterSupply[i-1];

                int actualHeight=arr[i];
                if(i>=cs){
                    actualHeight+=(waterSupply[i]-waterSupply[i-cs]);
                }
                else{
                    actualHeight+=waterSupply[i];
                }

                if(actualHeight<h){
                    waterSupply[i]+=(h-actualHeight);
                    days-=(h-actualHeight);
                }
                if(days<0){
                    return false;
                }
            }
            return true;
        }

        long long int maximizeMinHeight(vector<int> &a,int n,int k,int w){
            long long int res=-1;
            long long int mnHeight=*min_element(a.begin(),a.end());
            long long int mxHeight=INT_MAX/2;
            while(mnHeight<=mxHeight){
                int guessHeight=(mxHeight+mnHeight)/2;
                if(isOK(a,k,w,guessHeight)==true){
                    res=guessHeight;
                    mnHeight=guessHeight+1;
                }
                else{
                    mxHeight=guessHeight-1;
                }
            }
            return res;
        }
};