Arraygame

Level 4
Array Game
Có 1 trò chơi với dãy gồm N số như sau:

Mỗi bước đi bạn phải chia mảng thành 2 phần không rỗng sao cho tổng các phần tử bên trái bằng tổng phần tử bên phải. Nếu chia được bạn sẽ được 1 điểm, nếu không chia được trò chơi kết thúc.

Sau mỗi lần chia thành công, bạn phải bỏ 1 trong 2 phần đã chia và tiếp tục trò chơi với phần còn lại.

Cho 1 dãy, hỏi số điểm nhiều nhất mà bạn có thể thu được là bao nhiêu?

Input

Dòng đầu tiên là số lượng test case T (T <= 20).

Dòng đầu tiên của mỗi test case là N (N <= 20,000) là số lượng phần tử của dãy. Dòng tiếp theo là N phần tử của dãy đó.

 

Output

Mỗi test case in ra số điểm nhiều nhất mà có thể thu được

 

Sample

Input

3
3
3 3 3
4
2 2 2 2
7
4 1 0 1 1 0 1

Output

0
2
3


0
0
6
2
15
11
4
1
0
54
2
0
13
17
27
7
3
2
4
16106
Time: 0.500000000 s.
#include <iostream>
#include <time.h>
using namespace std;

int oo = 2000000000;

int T, n, arr[20001], result;

void backtrack(int left, int right, long long sum, int cnt){
	if(cnt > result) result = cnt;
	if(sum % 2 == 1 || left == right) return;

	long long tmp = 0;
	int i = left;
	while(i <= right){
		tmp += arr[i];
		if(tmp > sum/2) break;
		else if(tmp == sum/2){
			backtrack(left, i, tmp, cnt+1);
			backtrack(i+1, right, tmp, cnt+1);
			break;
		}
		i++;
	}
}


int main(){

	freopen("input.txt", "r", stdin);

	// Calc clock
	clock_t time_start, time_end; 
	time_start = clock(); 
	
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		// Initial && Input
		long long sum = 0;
		cin >> n;
		for(int i = 0; i < n; i++){
			cin >> arr[i];
			sum += arr[i];
		}
		result = 0;

		// Solve Problem
		if(!sum) result = n-1;
		else backtrack(0, n-1, sum, 0);
		
		// Output
		cout << result << endl;
	}

	// Calc Time
	time_end = clock();
	cout.setf(ios::fixed);
	cout.precision(9);
	cout << "Time: " << double (time_end - time_start) / double (CLOCKS_PER_SEC) << " s." << endl;
	
	return 0;
 }