Submission #75637672

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define inf 2e18
#define eps 1e-9
#define il inline
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int N=2e5+5,M=4e5+5;
const int mod=1e9+7;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,a[N],k;
inline bool check(int w){
	int res=0;
	for(int i=1;i<=n;i++){
		if(a[i]>=w) continue;
		int d=w-a[i];
		res=res+(d+i-1)/i;
		if(res>k) return false;
	}
	return res<=k;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int tc=1;
	while(tc--){
		cin>>n>>k;
		for(int i=1;i<=n;i++) cin>>a[i];
		int l=1,r=inf;
		while(l<r){
			int mid=(l+r+1)>>1;
			if(check(mid)) l=mid;
			else r=mid-1;
		}
		cout<<l<<'\n';
	} 
	
	return 0;
}

Submission Info

Judge Result