#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template < class S, class T> inline S divup_L( S a, T b) {
return ( a+ b- 1 ) / b;
}
#define main dummy_main
int main( ) {
return 0 ;
}
#undef main
class Solution{
public :
int smallestDivisor( vector< int > & nums, int threshold) {
int i;
int j;
int res;
int N = nums.size ( ) ;
long long s;
int Lj4PdHRW;
int KL2GvlyY;
int Q5VJL1cS;
Lj4PdHRW = 1 ;
KL2GvlyY = 1000000000 ;
while ( Lj4PdHRW < KL2GvlyY) {
if ( ( Lj4PdHRW + KL2GvlyY) % 2 == 0 ) {
Q5VJL1cS = ( Lj4PdHRW + KL2GvlyY) / 2 ;
}
else {
Q5VJL1cS = ( Lj4PdHRW + KL2GvlyY - 1 ) / 2 ;
}
s = 0 ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
s + = divup_L( nums[ i] ,Q5VJL1cS) ;
}
if ( s <= threshold) {
KL2GvlyY = Q5VJL1cS;
}
else {
Lj4PdHRW = Q5VJL1cS + 1 ;
}
}
res = KL2GvlyY;
return res;
}
}
;
// cLay varsion 20191214-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// class Solution {
// public:
// int smallestDivisor(vector<int>& nums, int threshold) {
// int i, j, res, N = nums.size();
// ll s;
// res = bsearch_min[int,x,1,1d9][
// s = 0;
// rep(i,N) s += nums[i] /+ x;
// ](s <= threshold);
// return res;
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPZmFzdCIpCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnRlbXBsYXRlPGNsYXNzIFMsIGNsYXNzIFQ+IGlubGluZSBTIGRpdnVwX0woUyBhLCBUIGIpewogIHJldHVybiAoYStiLTEpL2I7Cn0KI2RlZmluZSBtYWluIGR1bW15X21haW4KaW50IG1haW4oKXsKICByZXR1cm4gMDsKfQojdW5kZWYgbWFpbgpjbGFzcyBTb2x1dGlvbnsKICBwdWJsaWM6CiAgaW50IHNtYWxsZXN0RGl2aXNvcih2ZWN0b3I8aW50PiYgbnVtcywgaW50IHRocmVzaG9sZCl7CiAgICBpbnQgaTsKICAgIGludCBqOwogICAgaW50IHJlczsKICAgIGludCBOID0gbnVtcy5zaXplKCk7CiAgICBsb25nIGxvbmcgczsKICAgIGludCBMajRQZEhSVzsKICAgIGludCBLTDJHdmx5WTsKICAgIGludCBRNVZKTDFjUzsKICAgIExqNFBkSFJXID0gMTsKICAgIEtMMkd2bHlZID0gMTAwMDAwMDAwMDsKICAgIHdoaWxlKExqNFBkSFJXIDwgS0wyR3ZseVkpewogICAgICBpZigoTGo0UGRIUlcgKyBLTDJHdmx5WSklMj09MCl7CiAgICAgICAgUTVWSkwxY1MgPSAoTGo0UGRIUlcgKyBLTDJHdmx5WSkgLyAyOwogICAgICB9CiAgICAgIGVsc2V7CiAgICAgICAgUTVWSkwxY1MgPSAoTGo0UGRIUlcgKyBLTDJHdmx5WSAtIDEpIC8gMjsKICAgICAgfQogICAgICBzID0gMDsKICAgICAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICAgICAgcyArPWRpdnVwX0wobnVtc1tpXSxRNVZKTDFjUyk7CiAgICAgIH0KICAgICAgaWYocyA8PSB0aHJlc2hvbGQpewogICAgICAgIEtMMkd2bHlZID0gUTVWSkwxY1M7CiAgICAgIH0KICAgICAgZWxzZXsKICAgICAgICBMajRQZEhSVyA9IFE1VkpMMWNTICsgMTsKICAgICAgfQogICAgfQogICAgcmVzID1LTDJHdmx5WTsKICAgIHJldHVybiByZXM7CiAgfQp9CjsKLy8gY0xheSB2YXJzaW9uIDIwMTkxMjE0LTEKCi8vIC0tLSBvcmlnaW5hbCBjb2RlIC0tLQovLyAjZGVmaW5lIG1haW4gZHVtbXlfbWFpbgovLyB7fQovLyAjdW5kZWYgbWFpbgovLyAKLy8gY2xhc3MgU29sdXRpb24gewovLyBwdWJsaWM6Ci8vICAgaW50IHNtYWxsZXN0RGl2aXNvcih2ZWN0b3I8aW50PiYgbnVtcywgaW50IHRocmVzaG9sZCkgewovLyAgICAgaW50IGksIGosIHJlcywgTiA9IG51bXMuc2l6ZSgpOwovLyAgICAgbGwgczsKLy8gICAgIHJlcyA9IGJzZWFyY2hfbWluW2ludCx4LDEsMWQ5XVsKLy8gICAgICAgcyA9IDA7Ci8vICAgICAgIHJlcChpLE4pIHMgKz0gbnVtc1tpXSAvKyB4OwovLyAgICAgXShzIDw9IHRocmVzaG9sZCk7Ci8vICAgICByZXR1cm4gcmVzOwovLyAgIH0KLy8gfTsK