fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
  5. int t;
  6. long long n, k;
  7. vector<long long> v;
  8.  
  9. bool check(long long num) {
  10.     for (int i = 0; i < n; i++) {
  11.         vector<long long> v_c(v.begin(), v.end());
  12.         long long charge = k;
  13.         long long nn = num;
  14.         v_c[i] = nn;
  15.         for (int j = i; j < n; j++) {
  16.             if (v_c[j] <= v[j])return true;
  17.             if (j + 1 < n)v_c[j + 1] = v_c[j] - 1;
  18.             charge -= (v_c[j] - v[j]);
  19.             if (charge < 0)break;
  20.         }
  21.     }
  22.     return false;
  23. }
  24.  
  25. int main() {
  26.     fast;
  27.     cin >> t;
  28.     while (t--) {
  29.         cin >> n >> k;
  30.         v.resize(n);
  31.         for (auto &ele: v)cin >> ele;
  32.         long long l = 1, r = 1e9;
  33.         long long ans = 0;
  34.         while (l <= r) {
  35.             long long mid = (l + r) / 2;
  36.             if (!check(mid))r = mid - 1;
  37.             else ans = mid, l = mid + 1;
  38.         }
  39.         cout << ans << endl;
  40.     }
  41.     return 0;
  42. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DPLrGn
language:
C++14 (clang 8.0)
created:
4 days ago
visibility:
public

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!