fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool check(long long x, int n, const vector<long long>& h_original) {
  5.     vector<long long> h_current = h_original;
  6.     for (int i = n - 1; i >= 2; --i) {
  7.         if (h_current[i] < x) {
  8.             return false;
  9.         }
  10.         long long d = min(h_original[i] / 3LL, (h_current[i] - x) / 3LL);
  11.         h_current[i - 1] += d;
  12.         h_current[i - 2] += 2 * d;
  13.     }
  14.     return h_current[0] >= x && h_current[1] >= x;
  15. }
  16.  
  17. int main() {
  18.     ios_base::sync_with_stdio(false);
  19.     cin.tie(NULL);
  20.     int t;
  21.     cin >> t;
  22.     while (t--) {
  23.         int n;
  24.         cin >> n;
  25.         vector<long long> h(n);
  26.         for (int i = 0; i < n; ++i) {
  27.             cin >> h[i];
  28.         }
  29.  
  30.         long long low = 1, high = 1e9 + 7, ans = 0;
  31.         while (low <= high) {
  32.             long long mid = low + (high - low) / 2;
  33.             if (check(mid, n, h)) {
  34.                 ans = mid;
  35.                 low = mid + 1;
  36.             } else {
  37.                 high = mid - 1;
  38.             }
  39.         }
  40.         cout << ans << endl;
  41.     }
  42.     return 0;
  43. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4
4
1 2 10 100
4
100 100 100 1
5
5 1 1 1 8
6
1 2 3 4 5 6
stdout
copy 
7
1
1
3
https://ideone.com/17cx2c
language:
C++ (gcc 8.3)
created:
10 hours 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!