fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. #define ll long long int
  5. #define ld long double
  6. using namespace std;
  7. using namespace __gnu_pbds;
  8. #define FAST ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  9. typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
  10. const ll N = 1e5 + 5, MOD1 = 998244353, MOD2 = 1e9 + 7;
  11.  
  12. bool valid(vector<ll>&v, ll n, ll mid, ll k){
  13.     for(int i = 0;i<n;i++){
  14.         if((v[i] - 1) / mid <= k){
  15.             k -= (v[i] - 1) / mid;
  16.         }else{
  17.             return 0;
  18.         }
  19.     }
  20.     return 1;
  21. }
  22.  
  23. void solve(ld t) {
  24.     ll n, k;
  25.     cin >> n >> k;
  26.     vector<ll>v(n);
  27.     for(int i = 0;i<n;i++) cin >> v[i];
  28.     ll l = 0, r = 1e9 + 1, mid, ans;
  29.     while(l < r - 1){
  30.         mid = (l + r) >> 1;
  31.         if(valid(v,n,mid, k)){
  32.             ans = r = mid;
  33.         }else{
  34.             l = mid;
  35.         }
  36.     }
  37.     cout << ans;
  38. }
  39.  
  40. signed main() {
  41.     FAST
  42. #ifndef ONLINE_JUDGE
  43.     freopen("input.txt", "r", stdin);
  44.     freopen("output.txt", "w", stdout);
  45. #endif
  46.     int t = 1;
  47.     cin >> t;
  48.     for (ld i = 1; i <= t; i++) {
  49.         solve(i);
  50.         if (i < t) cout << "\n";
  51.     }
  52. }
Runtime error #stdin #stdout #stderr 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/CBQrqh
language:
C++14 (gcc 8.3)
created:
236 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!