Overview

Given that already occupied seats cannot be moved, we want to find the maximum number of additional people that can be seated in empty seats such that in the final state, no three consecutive seats are all \(1\).

Analysis

The constraint “must not create \(111\)” means that whether to set a seat to \(1\) depends on the state of the previous 2 seats. In other words, seat \(i\) can be set to \(1\) only when \((i-2, i-1, i)\) does not become \(111\) in the final state.

• A naive greedy approach of “filling empty seats as much as possible” can fail due to interactions with forced placements (seats that are originally \(1\)). For example, when \(S = [0, 0, 1]\), greedily filling from the left produces \([1, 1, 1]\), which is invalid. Since “the current choice changes the possibilities for the next (and subsequent) choices,” local decisions alone cannot guarantee optimality.
• On the other hand, in this problem, the feasibility of what to do with the next seat is determined as long as we know the state of the last 2 seats. Therefore, DP (dynamic programming) with a small number of states is effective.

Algorithm

Let \(T_1, \dots, T_N\) be the final state (\(T_i \in \{0, 1\}\)). Since already occupied seats must remain \(1\): - When \(S_i = 1\), \(T_i = 1\) is forced - When \(S_i = 0\), we can choose \(T_i \in \{0, 1\}\) (choosing \(1\) adds \(+1\) to the additional count)

DP State

We decide from left to right, keeping only the values of the last 2 seats as the state.

• \(dp[x][y]\): the maximum number of additionally seated people when the last 2 seats among those processed so far are \((x, y)\) (\(x, y \in \{0, 1\}\))

Here, “last 2 seats” means, for example, \((T_{i-1}, T_i)\) at the stage where we have decided up to seat \(i\).

Initially, nothing has been decided yet, so we treat seats \(-2, -1\) as \(0\) for convenience: - \(dp[0][0] = 0\) (all others are unreachable)

Transitions

For seat \(i\) (0-indexed in code), the possible values \(z = T_i\) are: - If \(S_i = 1\), only \(z = 1\) - If \(S_i = 0\), \(z \in \{0, 1\}\)

However, due to the constraint: - \((x, y, z) = (1, 1, 1)\) is forbidden (would create 3 consecutive \(111\))

If allowed, we transition to the next state \((y, z)\). The additional count is: - \(+1\) only when \(S_i = 0\) and \(z = 1\) (a new person seated in an empty seat)

We perform this for all seats, and the answer is \(\max_{x,y} dp[x][y]\) at the end.

Complexity

• Time complexity: \(O(N)\) (For each seat, a constant number of transitions: \(4\) states × at most \(2\) choices)
• Space complexity: \(O(1)\) (We only update a \(2 \times 2\) DP array to a next array)

Implementation Notes

• Initialize unreachable states with a very small value (NEG = -10**18 in the code) to safely write the maximization DP.

• A useful trick is to pad the beginning by assuming “the previous 2 seats are initially \((0, 0)\)” (dp[0][0] = 0) to simplify boundary handling.

• Seats with \(S_i = 1\) are fixed to \(z = 1\), and are not counted toward the additional number (since the person was already seated there).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    S = list(map(int, input().split()))

    NEG = -10**18
    dp = [[NEG, NEG], [NEG, NEG]]
    dp[0][0] = 0  # padding zeros for positions -2, -1

    for i in range(N):
        ndp = [[NEG, NEG], [NEG, NEG]]
        if S[i] == 1:
            choices = (1,)
        else:
            choices = (0, 1)

        for x in (0, 1):
            for y in (0, 1):
                cur = dp[x][y]
                if cur == NEG:
                    continue
                for z in choices:
                    if x == 1 and y == 1 and z == 1:
                        continue
                    add = 1 if (z == 1 and S[i] == 0) else 0
                    if cur + add > ndp[y][z]:
                        ndp[y][z] = cur + add
        dp = ndp

    ans = max(dp[0][0], dp[0][1], dp[1][0], dp[1][1])
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.