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?
@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