Maximize the smallest array element by incrementing all elements in a K | C ++ program for above approach ; Function to check if the smallest value of v is achievable or not ; Create array to store previous moves ; Remove previous moves ; Add balance to ans ; Update contiguous subarray of length k ; Number of moves should not exceed m ; Function to find the maximum value of the smallest array element that can be obtained ; Perform Binary search ; Driver Code ; Given Input ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long NEW_LINE ll n , m , k , l , r , i ; ll check ( ll v , vector < ll > & a ) { ll tec = 0 , ans = 0 ; vector < ll > b ( n + k + 1 ) ; for ( i = 0 ; i < n ; i ++ ) { tec -= b [ i ] ; if ( a [ i ] + tec < v ) { ll mov = v - a [ i ] - tec ; ans = ans + mov ; tec += mov ; b [ i + k ] = mov ; } } return ( ans <= m ) ; } ll FindLargest ( vector < ll > a ) { l = 1 ; r = pow ( 10 , 10 ) ; while ( r - l > 0 ) { ll tm = ( l + r + 1 ) / 2 ; if ( check ( tm , a ) ) l = tm ; else r = tm - 1 ; } return l ; } int main ( ) { vector < ll > a { 2 , 2 , 2 , 2 , 1 , 1 } ; m = 2 ; k = 3 ; n = a . size ( ) ; cout << FindLargest ( a ) ; return 0 ; }