1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    string s; cin >> s;
    vector<int> A, B;

    int i = n-1; while (i >= 0 and s[i] == '0') {--i; s.pop_back(); };
    if (i != n-1) B.push_back(n-1-i);
    n = s.size();
    i = 0; while (i < s.size() and s[i] == '0') ++i;
    if (i and i != n-1) B.push_back(i);

    for (int j = i; j < n;) {
      if (s[j] == '0') {
        int k = j+1;
        while (k < n and s[k] == '0') ++k;
        A.push_back(k-j);
        j = k+1;
      }
      else ++j;
    }

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    vector<int> pref((n/2) + 10), fq(n+1);
    for (auto &x : A) {
      pref[(x + 1) >> 1]++;
      ++fq[x];
    }
    for (int j = pref.size()-1; j >= 0; --j) {
      if (pref[j] and pref[j+1]) pref[j] += 1;
    }
    
    A.push_back(0);
    B.push_back(0);

    long long res = 0, S_A = 0;
    for (int k = A.size() - 1; k >= 0; --k) {
      const long long Ap = A.size() - k - 1;
      S_A += A[k];
      long long S_B = 0;
      for (int l = B.size() - 1; l >= 0; --l) {
        const long long Bp = B.size() - l - 1;
        const int marked = 2*Ap + Bp;

        S_B += B[l];
        long long sum = S_A + S_B 
                      - Ap*(2*Ap - 1) 
                      - Bp*(Bp-1)/2 
                      - 2*Ap*Bp;
        // 
        res = max(res, sum);
      }
    }

    cout << res;
  }
}