Overview

Given \(N\) flower beds arranged in a row, the problem asks to maximize the total beauty of selected flower beds under the condition that “no two adjacent flower beds may be selected simultaneously.”

Analysis

First, a naive approach would be to “try all possible combinations.” However, since each flower bed has 2 choices — “plant or not plant” — the total number of combinations is \(2^N\). Given the constraint \(N \leq 2 \times 10^5\), this approach takes too long to compute (TLE).

The key insight of this problem is that “when deciding whether to plant flowers in the \(i\)-th flower bed, it suffices to have information about the optimal selection for all preceding flower beds.”

When focusing on the \(i\)-th flower bed, the choices are limited to the following two: 1. Plant flowers in the \(i\)-th flower bed: Since adjacent flower beds cannot both be planted, the \((i-1)\)-th flower bed cannot be planted. Therefore, the total beauty is “maximum value up to the \((i-2)\)-th flower bed + \(A_i\).” 2. Do not plant flowers in the \(i\)-th flower bed: In this case, there is no constraint impact. Therefore, the total beauty directly inherits “the maximum value up to the \((i-1)\)-th flower bed.”

In this way, dynamic programming (DP), a technique that decomposes a large problem into smaller subproblems, is effective.

Algorithm

Dynamic Programming (DP)

We define the DP as follows: - \(dp[i]\): the maximum total beauty when considering up to the \(i\)-th flower bed

The transition formula is as follows: $\(dp[i] = \max(dp[i-1], dp[i-2] + A_i)\)$

Space Optimization

If we naively create an array \(dp\), it requires memory of length \(N\). However, looking at the formula, computing \(dp[i]\) only requires two values: \(dp[i-1]\) and \(dp[i-2]\). Therefore, by maintaining the state with just two variables (dp_prev1, dp_prev2) while iterating through the loop, we can save memory usage.

Complexity

• Time Complexity: \(O(N)\) The computation completes with just a single loop over the \(N\) flower beds, making it very fast.
• Space Complexity: \(O(N)\) \(O(N)\) memory is used to store the input array \(A\). The DP computation itself can be done with \(O(1)\) additional variables.

Implementation Notes

• Fast Input: In Python, when \(N\) is large, reading all input at once using sys.stdin.read().split() is faster than repeatedly calling input(), reducing execution time.

• Initial Values: When \(i=1\), the index \(i-2\) does not exist, so by treating the initial value as \(0\), we can handle all cases uniformly within the loop.

• Handling Large Numbers: Python natively supports arbitrary-precision integers, so even when the total value reaches approximately \(10^{14}\) (\(10^9 \times 2 \times 10^5\)), we can compute without worrying about overflow.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # sys.stdin.read().split() は高速に大量の入力を読み込むのに適しています
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は何もせず終了
    if not input_data:
        return
    
    # 1番目の要素は花壇の数 N
    n = int(input_data[0])
    
    # 2番目以降の要素は各花壇の美しさ A_i
    # map(int, ...) を使って効率的に整数に変換する
    a_values = map(int, input_data[1:n+1])
    
    # 動的計画法（DP）を用いて最大値を求める
    # dp_prev2: i-2 番目の花壇までを考慮したときの最大美しさ
    # dp_prev1: i-1 番目の花壇までを考慮したときの最大美しさ
    dp_prev2 = 0
    dp_prev1 = 0
    
    # 各花壇の美しさについて順番に処理を行う
    for a_i in a_values:
        # i 番目の花壇に花を植えるかどうかの2択を考える
        # 1. 花を植えない場合: 合計の美しさは i-1 番目までの最大値 (dp_prev1) と同じ
        # 2. 花を植える場合: 隣り合う花壇には植えられないため、i-2 番目までの最大値 (dp_prev2) に 
        #    現在の美しさ a_i を加えたものになる
        
        option_not_plant = dp_prev1
        option_plant = dp_prev2 + a_i
        
        # 2つの選択肢のうち、大きい方を現在の最大値とする
        if option_not_plant > option_plant:
            current_max = option_not_plant
        else:
            current_max = option_plant
            
        # 次のループ（i+1番目の花壇）に向けて状態を更新する
        dp_prev2 = dp_prev1
        dp_prev1 = current_max
        
    # すべての花壇を考慮した後の最大値を出力する
    print(dp_prev1)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.