Overview

Given \(N\) seats arranged in a row, under the constraint that no three consecutive seats are all occupied, we want to seat as many new people as possible in the empty seats. We use dynamic programming (DP) to find the maximum number of people.

Analysis

Key Insight

The key point of this problem is the constraint that “no three consecutive seats may all be \(1\).” When deciding whether to seat someone in seat \(i\), the decision depends only on the states of the two immediately preceding seats.

Specifically, as long as seats \(i-2, i-1, i\) are not all \(1\), whether we can set seat \(i\) to \(1\) depends only on the states of seats \(i-2\) and \(i-1\).

Problem with the Naive Approach

Enumerating all empty seats and trying all patterns (\(2^{(\text{number of empty seats})}\) possibilities) is far too slow since \(N\) can be up to \(2 \times 10^5\).

Solution Strategy

Since only the states of the two preceding seats matter, we can solve this with a DP with very few states. The state of the two preceding seats is represented by the pair \((T_{i-2}, T_{i-1})\), and since each value is either \(0\) or \(1\), there are only \(4\) states: \((0,0), (0,1), (1,0), (1,1)\).

Algorithm

1. DP Definition: Let \(dp[(a, b)]\) be “the maximum number of newly seated people when all seats up to the current one have been processed and the states of the last two seats are \((a, b)\).”

2. Initial State: Before processing any seats, we use a virtual state \((0, 0)\) and initialize \(dp[(0, 0)] = 0\).

3. Transition: When processing seat \(i\):

   • If \(S_i = 1\) (already occupied): only \(T_i = 1\) is possible.
   • If \(S_i = 0\) (empty): two choices — \(T_i = 0\) (leave empty) or \(T_i = 1\) (seat a new person).

For each state \((a, b)\) and choice \(t = T_i\), if \(a = 1\) and \(b = 1\) and \(t = 1\), this violates the constraint, so we skip it. If there is no violation, we transition to the new state \((b, t)\) and add the number of newly seated people \(t - S_i\) (\(1\) when \(S_i = 0\) and \(t = 1\), \(0\) otherwise).

1. Answer: The maximum value among all \(dp\) entries after processing all seats is the answer.

Concrete Example

Consider \(N = 5, S = [0, 1, 0, 0, 1]\).

• Seat 1: Empty, so we can choose \(0\) or \(1\) → choose \(1\)
• Seat 2: Already \(1\) → stays \(1\)
• Seat 3: Empty, but seats 1 and 2 are \((1,1)\), so we cannot set it to \(1\) → \(0\)
• Seat 4: Empty, preceding seats are \((1,0)\), so we can set it to \(1\) → \(1\)
• Seat 5: Already \(1\), preceding seats are \((0,1)\), so OK → \(1\)

Result: \(T = [1, 1, 0, 1, 1]\), number of newly seated people is \(2\).

Complexity

• Time complexity: \(O(N)\) — At each seat, the number of states is at most \(4\) and the number of choices is at most \(2\), so each step is \(O(1)\).
• Space complexity: \(O(1)\) — The DP table always has at most \(4\) entries. (Storing the input requires \(O(N)\).)

Implementation Notes

• By managing the DP states with a dictionary (a, b) -> maximum number of newly seated people, we can take advantage of the small number of states for a simple implementation.

• By introducing the virtual initial state \((0, 0)\), we avoid special-casing the processing of the first elements of the array.

• Don’t forget that when \(S_i = 1\), we cannot set \(T_i = 0\) (we cannot ask a customer to leave their seat).

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    S = [int(input_data[i + 1]) for i in range(N)]
    
    # dp[i][last2][last1] = max number of new people added considering seats 0..i
    # last2, last1 are the states of seat i-1 and seat i respectively
    # We want to maximize the number of 1s we add (T[i] - S[i] for each i)
    
    # States: (prev2, prev1) where prev2 = T[i-1], prev1 = T[i]
    # Transition: for seat i+1, new state is (prev1, T[i+1])
    # Constraint: not (prev2 == 1 and prev1 == 1 and T[i+1] == 1)
    # Also: if S[i+1] == 1, then T[i+1] must be 1
    
    # dp stored as dict (prev2, prev1) -> max added people
    # Initialize with a virtual state before seat 0
    
    NEG_INF = -1
    
    # Before processing any seat, we have no previous seats
    # We'll use prev2=-1, prev1=-1 to indicate no previous seats
    # Better: process seat by seat
    
    # dp[(a, b)] = max added, where a = T[i-2], b = T[i-1] after processing seats 0..i-1
    # For i=0, before processing, state is (0, 0) as virtual seats before the array
    
    dp = {}
    dp[(0, 0)] = 0  # virtual previous states
    
    for i in range(N):
        new_dp = {}
        s = S[i]
        
        if s == 1:
            candidates = [1]  # must remain 1
        else:
            candidates = [0, 1]  # can choose to seat someone or not
        
        for (a, b), val in dp.items():
            for t in candidates:
                if a == 1 and b == 1 and t == 1:
                    continue  # violates constraint
                added = val + (t - s)  # t - s is 1 if we added someone, 0 otherwise (t >= s always)
                key = (b, t)
                if key not in new_dp or new_dp[key] < added:
                    new_dp[key] = added
        
        dp = new_dp
    
    print(max(dp.values()))

solve()

---

This editorial was generated by claude4.6opus-thinking.