#include <bits/stdc++.h> using namespace std; typedef long long int ll; const int N = 2e5 + 5; const int LIM = 1<<20; int A[N]; ll Check2(ll used, ll left, ll cnt) { ll sol = used * cnt * left; sol += ((cnt * (cnt - 1)) / 2) * (used + left); sol += (cnt * (cnt - 1) * (cnt - 2)) / 6; return sol; } int BinSearch(int used, int K, ll need) { int beg = -1, end = K, mid; while(end - beg > 1) { mid = (beg + end) / 2; if(Check2(used, K - mid, mid) >= need) end = mid; else beg = mid; } return end; } bool Check(int K, int n) { int used = 0; for(int i = 0; i < n; i++) { int help = BinSearch(used, K, A[i]); if(Check2(used, K - help, help) < A[i]) return false; used += help; K -= help; } return true; } int Solve(int n) { int beg = 0, end = LIM, mid; while(end - beg > 1) { mid = (beg + end) / 2; if(Check(mid, n)) end = mid; else beg = mid; } return end; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t, n; cin >> t; while(t --> 0) { cin >> n; for(int i = 0; i < n; i++) cin >> A[i]; cout << Solve(n) << "\n"; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #include <bits/stdc++.h> using namespace std; typedef long long int ll; const int N = 2e5 + 5; const int LIM = 1<<20; int A[N]; ll Check2(ll used, ll left, ll cnt) { ll sol = used * cnt * left; sol += ((cnt * (cnt - 1)) / 2) * (used + left); sol += (cnt * (cnt - 1) * (cnt - 2)) / 6; return sol; } int BinSearch(int used, int K, ll need) { int beg = -1, end = K, mid; while(end - beg > 1) { mid = (beg + end) / 2; if(Check2(used, K - mid, mid) >= need) end = mid; else beg = mid; } return end; } bool Check(int K, int n) { int used = 0; for(int i = 0; i < n; i++) { int help = BinSearch(used, K, A[i]); if(Check2(used, K - help, help) < A[i]) return false; used += help; K -= help; } return true; } int Solve(int n) { int beg = 0, end = LIM, mid; while(end - beg > 1) { mid = (beg + end) / 2; if(Check(mid, n)) end = mid; else beg = mid; } return end; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t, n; cin >> t; while(t --> 0) { cin >> n; for(int i = 0; i < n; i++) cin >> A[i]; cout << Solve(n) << "\n"; } return 0; } |