problemB.cpp

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <stack>
#include <functional>
#include <set>
#include <math.h>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <cstdio>
#include <sstream>
#define ll long long int
#define ld long double
#define fr(i, a, b) for(int i = a; i < b; i++)
#define frb(i, a, b) for(int i = a; i >= b; i--)
#define sq(x) ((x) * (x))
#define PI ( acos(-1.0) )
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define px first
#define py second
using namespace std;

int t;
int n;
int *seg;
int seg_sz; // 8
void seg_init() {
	int t = ceil(log2(n)) + 1; // 3
	seg_sz = 1 << t;
	seg = new int[seg_sz];
	memset(seg, 0, sizeof(int) * seg_sz);
}

int seg_sum(int nw, int l, int r,int start, int end) {
	if (l > end || r < start) {
		return 0;
	}
	if (l <= start && end <= r) {
		return seg[nw];
	}
	int mid = (start + end) / 2;
	return seg_sum(nw * 2, l, r, start, mid) + seg_sum(nw * 2 + 1, l, r, mid + 1, end);
}

void solve() {
	cin >> n;
	seg_init();

	int idx = seg_sz / 2; // 4 5 6 7
	fr(i, 0, n) {
		char t;
		cin >> t;
		seg[idx + i] = (t - '0');
	}
	frb(i, idx - 1, 1) {
		int left = i * 2;
		int right = i * 2 + 1;
		seg[i] = seg[left] + seg[right];
	}

	int k = (n + 1) / 2 - 1;
	int ans = 0;
	int tsz = seg_sz / 2;

	fr(i, 1, n - k + 1) {
		ans = max(ans, seg_sum(1, i, i + k, 1, tsz));
	}
	cout << ans << "\n";
	delete[] seg;
}

void init() {
	cin >> t;
	fr(i, 0, t) {
		cout << "Case #" << i+1 << ": ";
		solve();
	}
}



int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	init();
	//solve();
	system("pause");
	return 0;
}