Mahmoud_Hawara

Untitled

Aug 1st, 2022
171
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #pragma GCC optimize("-Ofast")
  4. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
  5. #pragma GCC optimize("-ffast-math")
  6. #pragma GCC optimize("-funroll-loops")
  7. #pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")
  8. #define IO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  9. const long long MOD = 1e9 + 7, OO = 1e18;
  10. const double PI = acos(-1);
  11. const int N = 1e3 + 5;
  12. const int dx[4] = {0, 0, 1, -1};
  13. const int dy[4] = {1, -1, 0, 0};
  14.  
  15. long long t, n, h, a[N], l, r, md;
  16.  
  17. bool ok(long long k)
  18. {
  19.     long long sm = 0;
  20.     for (int i = 1; i < n; i++)
  21.     {
  22.         sm += min(a[i + 1] - a[i], k);
  23.     }
  24.     sm += k;
  25.  
  26.     return sm >= h;
  27. }
  28.  
  29. int main()
  30. {
  31.     IO
  32.     cin >> t;
  33.     while (t--)
  34.     {
  35.         cin >> n >> h;
  36.         for (int i = 1; i <= n; i++)
  37.         {
  38.             cin >> a[i];
  39.         }
  40.         l = 1, r = 1e18;
  41.         while (l < r)
  42.         {
  43.             md = (l + r) / 2;
  44.             if (ok(md))r = md;
  45.             else l = md + 1;
  46.         }
  47.         cout << l << '\n';
  48.     }
  49.     return 0;
  50. }
  51.  
Advertisement
Add Comment
Please, Sign In to add comment