Untitled

 avatar
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