Advertisement
Josif_tepe

Untitled

Mar 21st, 2024
469
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.84 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. typedef long long ll;
  5. const int maxn = 20005;
  6. ll pref_sum[maxn];
  7. ll query(int i, int j) {
  8.     if(i == 0) {
  9.         return pref_sum[j];
  10.     }
  11.     return pref_sum[j] - pref_sum[i - 1];
  12. }
  13. int rec(int L, int R) {
  14.     for(int i = L; i < R; i++) {
  15.         if(pref_sum[i] * 2 == pref_sum[R] + pref_sum[L - 1]) {
  16.             return max(rec(L, i), rec(i + 1, R)) + 1;
  17.         }
  18.     }
  19.     return 0;
  20.  
  21. }
  22. int main() {
  23.     int t;
  24.     cin >> t;
  25.     while(t--) {
  26.         int n;
  27.         cin >> n;
  28.         memset(pref_sum, 0, sizeof pref_sum);
  29.         ll sum = 0;
  30.         for(int i = 0; i < n; i++) {
  31.             int x;
  32.             cin >> x;
  33.             sum += x;
  34.             pref_sum[i] = sum;
  35.         }
  36.         cout << rec(0, n - 1) << endl;
  37.        
  38.     }
  39.    
  40.     return 0;
  41. }
  42.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement