#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; } }
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; } } |