Overview

You are given the initial state of \(N\) seats. The problem asks you to find the maximum number of people you can additionally seat in empty seats, such that no three consecutive seats are all occupied.

Approach

Consider deciding from left to right whether to seat a person in each empty seat (set it to \(1\)) or leave it empty (keep it \(0\)). Due to the constraint that “no three consecutive seats may all be \(1\),” whether a person can be seated at a given seat depends only on the states of the two most recent seats.

If we perform a brute-force search over all empty seats, the time complexity would be \(O(2^K)\) where \(K\) is the number of empty seats, which in the worst case becomes \(O(2^N)\) and results in TLE (Time Limit Exceeded). However, by noting that we only need to keep track of the states of the two most recent seats (\(00, 01, 10, 11\) — 4 possibilities), we can solve this efficiently using dynamic programming (DP).

Algorithm

We use dynamic programming (DP). Define the following DP table:

\(DP[j][k] = \) “the maximum number of newly seated people when the seat two positions back has state \(j\) and the seat one position back has state \(k\)” (\(j, k \in \{0, 1\}\))

As the initial state, we imagine two virtual empty seats to the left of all seats, setting \(DP[0][0] = 0\) and all other entries to \(-\infty\).

For each seat \(i\) (with initial state \(S_i\)), we consider what the final state \(l \in \{0, 1\}\) of seat \(i\) should be, and perform transitions satisfying the following conditions:

1. No removal condition: When \(S_i = 1\), a person is already seated, so we cannot set \(l = 0\).
2. Ventilation rule condition: If \(j = 1\), \(k = 1\), and \(l = 1\), three consecutive people would be seated, so this transition is not allowed.

Only when these conditions are satisfied do we update the next DP table \(ndp[k][l]\). When a previously empty seat (\(S_i = 0\)) is newly occupied (\(l = 1\)), the count of seated people increases by \(1\), so we add \(+1\) to the transition source value.

\[ndp[k][l] = \max(ndp[k][l], DP[j][k] + \text{add})\]

(where \(\text{add}\) is \(1\) when \(S_i = 0\) and \(l = 1\), and \(0\) otherwise)

After processing all seats in order, the maximum value remaining in the DP table is the answer.

Complexity

• Time complexity: \(O(N)\)
  • For each seat, we only compute transitions over all combinations of \(j, k, l\) (\(2 \times 2 \times 2 = 8\) possibilities), so the processing time is proportional to the number of seats \(N\).
• Space complexity: \(O(1)\)
  • Since we only maintain the DP table from the previous step (a \(2 \times 2\) array) and reuse it, the memory usage is constant.

Implementation Notes

• Excluding unreachable states: By initializing the DP table values to -INF (a sufficiently small value), we can simply prevent erroneous transitions from states that have not yet been reached.

• Array updates: By preparing separate arrays for the current step’s dp and the next step’s ndp, and replacing dp = ndp after finishing the computation for each seat, we prevent states from getting mixed up during computation.

  Source Code

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    S = [int(x) for x in data[1:]]

    INF = float('inf')
    dp = [[-INF] * 2 for _ in range(2)]
    dp[0][0] = 0

    for s in S:
        ndp = [[-INF] * 2 for _ in range(2)]
        for j in range(2):
            for k in range(2):
                if dp[j][k] == -INF:
                    continue
                for l in range(2):
                    if s == 1 and l == 0:
                        continue
                    if j == 1 and k == 1 and l == 1:
                        continue
                    
                    add = 1 if s == 0 and l == 1 else 0
                    if dp[j][k] + add > ndp[k][l]:
                        ndp[k][l] = dp[j][k] + add
        dp = ndp

    ans = max(max(row) for row in dp)
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.