Untitled
unknown
plain_text
a year ago
1.0 kB
3
Indexable
#include<iostream> using namespace std; long t,n,mang[20000],ans; long long sum; int findMid(int l, int r, long long s){ long long a=0; for(int i=l; i<=r; i++){ a+=mang[i]; if(a==s/2) return i; } return -1; } void bt(int start, int end, int dem, long long csum){ if(csum % 2 != 0){ if(dem > ans) ans = dem; return; } if(left>=right){ if(dem > ans) ans = dem; return; } int mid = findMid(start, end, csum); if(mid == -1){ if(dem > ans) ans = dem; return; } for(int i=0; i<2; i++){ if(i==0){ bt(start, mid, dem+1, csum/2); }else{ bt(mid+1, end, dem+1, csum/2); } } } int main(){ freopen("Text.txt", "r", stdin); cin >> t; for(int tc=1; tc<=t; tc++){ cin >> n; sum=0; for(int i=0; i<n; i++){ cin >> mang[i]; sum+=mang[i]; } ans=0; if(sum % 2 != 0) cout << "0" << endl; else if(sum==0){ cout << n-1 << endl; }else{ bt(0,n-1,0,sum); cout << ans << endl; } } return 0; }
Editor is loading...
Leave a Comment