Untitled
unknown
plain_text
a year ago
1.3 kB
1
Indexable
Never
#include <iostream> using namespace std; long long arr[20001]; long long sum(int i , int j) // tinh tong tu i den j { long long sm = 0; for(int k = i; k <= j; k++) { sm = sm + arr[k]; } return sm; } void devide(int cnt, int xbgin, int xend, int &max) { long long N1 = sum(xbgin, xend); long long sm = 0; int index = -1; if(max <cnt) { max = cnt; } if(xbgin >= xend) { return; } // tim vi tri chinh giua cua phan tu for(int i = xbgin; i <= xend; i++) { sm = sm + arr[i]; if(sm == N1 / 2 && sm != 0) { cnt++; index = i; break; } } if(index != -1) { for(int i = 0; i <= 1; i++) { if(i == 0) { //chon bo phan thu 1 devide(cnt, index + 1, xend, max); } else { //lay phan thu nhat devide(cnt, xbgin, index, max); } } } else return; } int main() { freopen("input.txt", "r", stdin); int testcase; cin >> testcase; for(int tc = 1; tc <= testcase; tc++) { int N; cin >> N; for(int i = 0; i < N; i++) { cin >> arr[i]; } int max = 0; devide(0, 0,N - 1, max); if(sum(0, N -1) == 0) { max = N -1; } cout<<max<<endl; } }