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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int>> intervals;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int t, n;

  cin >> t;

  for (int test_case = 0; test_case < t; test_case++) {
    cin >> n;

    int length = 0;
    bool first_one = true;
    int ones_count = 0;
    for (int i = 0; i < n; i++) {
      char c;
      cin >> c;
      if (c == '1') {
        if (length > 0) {
          intervals.emplace_back(first_one ? length : length / 2, length);
        }
        first_one = false;
        ones_count++;
        length = 0;
      }
      else {
        length++;
      }
    }

    if (ones_count == 0) {
      cout << "0\n";
      continue;
    }

    if (length > 0) {
      intervals.emplace_back(length, length);
    }

    sort(intervals.begin(), intervals.end(), greater<>());

    int time = 0;
    int result = ones_count;

    for (auto interval: intervals) {
      if (interval.second != interval.first) {
        int lost = min(time * 2, interval.second);
        result += lost;

      if (lost <= interval.second - 1)
        time++;

      if (lost <= interval.second - 2)
        result++;

      if (lost <= interval.second - 3)
        time++;
      }
      else {
        int lost = min(time, interval.second);
        result += lost;

        if (lost < interval.second)
          time++;
      }
    }

    cout << result << "\n";
    intervals.clear();
  }

  return 0;
}