Help me solve this problem

An array has N integers (a1,a2,…,an) we have to perform operations on this array ,
In one operation you have to pic a subarray of size K and add 1 to every element in the
subarray.We can do atmost P operations on this array
Goal is to maximize the minimum element in the array .
Find the minimum element after perform P such operations

Constraints:
1<=k<=N<=10^5
1<=p<=10^5

Input:
N K P
Array of size N

Test case:
5 2 4
5 4 3 2 1

Ouput:
4

Explanation:

minimum value can be 4 after 4 operations of incrementing 2 elements each time.

@cubefreak777 can you help?

Problem link ?

@cubefreak777 This problem is not from any ongoing contests

Did you try binary search, I think it could be easily solved by it.

1 Like

@cubefreak777 I dont know how to use binary search much so i didnt try

I mean just ask the question if you can have the minimum element at least equal to some x or not. then it’s trivial prefix sums.

UNTESTED_CODE
#include "bits/stdc++.h"
#define int long long 
using namespace std ;
const int mxN=1e5 ;
int n,k,p,a[mxN+1] ;
signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);     
  cin>>n>>k>>p ;
  for(int i=1;i<n+1;i++)
  	cin>>a[i] ;
  // ask if it's possible to have the minimum element atleast equal to x
  auto ok=[&](int x){
  	vector<int>pr(n+2) ;
  	int ans=0 ;
  	for(int i=1,d;i<=n;i++){
  		pr[i]+=pr[i-1] ;
  		d=max(x-a[i]-pr[i],0LL) ;
  		ans+=d;
  		pr[i]+=d;pr[min(i+k,n+1)]-=d ;	
  	}
  	return ans<=k  ;
  }   ;
  int lb=1,rb=1e9+1 ;
  while(lb<rb){
  	int mb=(lb+rb)/2 ;
  	ok(mb)?lb=mb+1:rb=mb  ;
  }
  cout<<lb  ;
}

2 Likes

@cubefreak777 Thanks a lot for always being there to help😊

1 Like