Overview

Convert whether a “footprint (dust decreases)” is left when stepping on each tile into a 0/1 cost, and solve it as a minimum cost path problem from tile \(1\) to \(N\) with steps of 1 or 2 tiles using dynamic programming.

Analysis

Organizing the Conditions for Leaving Footprints

When you step on tile \(i\), the dust decreases by \(D_i\), but the decrease is at most the current thickness.
In this problem, movement is always to the right (\(+1\) or \(+2\)), so you cannot go back and step on the same tile again, meaning each tile is stepped on at most once.
Therefore, whether “the dust decreased after stepping on tile \(i\)” is determined solely by the initial values.

• If the initial dust is \(H_i = 0\), stepping on it causes no decrease (no footprint)
• If the decrease amount is \(D_i = 0\), stepping on it causes no decrease (no footprint)
• If \(H_i > 0\) and \(D_i > 0\), the dust necessarily decreases by at least 1 (footprint left)

Therefore, by assigning the following 0/1 cost to each tile: [ A_i = \begin{cases} 1 & (H_i>0 \ \text{and}\ D_i>0)\ 0 & \text{otherwise} \end{cases} ] the “number of footprints” equals “the sum of \(A_i\) over the tiles visited.”

Why a Naive Approach is Difficult

The combinations of movement methods (1 step or 2 steps) grow exponentially. For example, since there are 2 choices at each position, exhaustive enumeration would require close to \(2^{N}\) searches in the worst case, which is far too slow for \(N \le 2\times 10^5\).

Therefore, we use dynamic programming that computes sequentially from the front using “the minimum number of footprints to reach position \(i\).”

Algorithm

DP Definition

[ dp[i] = \text{the minimum number of footprints when reaching tile } i ]

Since the ways to reach tile \(i\) are either one step from \(i-1\) or two steps from \(i-2\): [ dp[i] = A_i + \min(dp[i-1],\ dp[i-2]) \quad (i\ge 3) ]

For initial conditions, noting that the starting tile must be stepped on: - \(dp[1] = A_1\) - \(dp[2] = dp[1] + A_2\) (to reach tile 2, you must go 1→2 and step on it)

The final answer is \(dp[N]\).

Concrete Example (Illustration)

For example, if \(A = [1,0,1,1]\) (tiles 1, 3, 4 leave footprints), then: - Going 1→3→4 gives footprints \(A_1+A_3+A_4 = 3\) - Going 1→2→4 gives footprints \(A_1+A_2+A_4 = 2\)

The DP automatically selects this minimum value.

Complexity

• Time complexity: \(O(N)\) (constant number of updates for each \(i\))
• Space complexity: \(O(N)\) (for the \(dp\) array)

Implementation Notes

• Since “a footprint is left” only when \(H_i>0\) and \(D_i>0\), converting to an array \(A\) (0/1) beforehand simplifies the DP.

• Since there can be small cases like \(N=2\), initialize \(dp[2]\) safely with proper conditional branching.

• In Python, using 1-indexed \(dp\) (length \(N+1\)) and mapping to 0-indexed array \(A\) with A[i-1] reduces implementation errors.

  Source Code

import sys

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

    A = [1 if (h > 0 and d > 0) else 0 for h, d in zip(H, D)]

    INF = 10**18
    dp = [INF] * (N + 1)  # 1-indexed
    dp[1] = A[0]
    if N >= 2:
        dp[2] = dp[1] + A[1]
    for i in range(3, N + 1):
        dp[i] = A[i - 1] + min(dp[i - 1], dp[i - 2])

    print(dp[N])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.