Submission #15619338

---

Source Code Expand

#include <bits/stdc++.h>
#define x first
#define y second
#define int int long long // 2e9 & 9e18
using namespace std; const int inf = numeric_limits<int>::max();
struct __io{__io(){ios_base::Init i; ios_base::sync_with_stdio(0); cin.tie(0);}} __io; // fast I/O
#ifdef LOCAL // setting up print debugging (yes lol)
template<class K, class V>ostream& operator<<(ostream&s,const pair<K,V>&p){s<<'<'<<p.x<<", "<<p.y<<'>';return s;}
template<class T, class=typename T::value_type, class=typename enable_if<!is_same<T,string>::value>::type>
ostream& operator<<(ostream&s,const T&v){s<<'[';for(auto&x:v){s<<x<<", ";}if(!v.empty()){s<<"\b\b";}s<<']';return s;}
void __prnt(){cerr<<endl;} template<class T, class...Ts>void __prnt(T&&a,Ts&&...etc){cerr<<a<<' ';__prnt(etc...);}
#define print(...) __prnt(__VA_ARGS__)
#else
#define print(...)
#endif

bool ok(vector<int> &a, double x, int k) {
	int k0;
	for (int d : a) {
		k0 = ceil(d / (x )) - 1;
		if (round(d / (k0 + 1)) > x) {
			k0++;
		}
		k -= k0;
	}

	return k >= 0;
}

signed main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int l = 0;
    int r = 1000000001;
    int m;
    while (l < r - 1) {
    	m = l + (r - l) / 2;
    	if (ok(a, m, k)) {
    		r = m;
    	} else {
    		l = m;
    	}
    }
    cout << r << endl;
}

Submission Info

Judge Result