Codeforces 478D Red Green Towers - Implementation

Here is the implementation for Red Green Towers (Codeforces 478D):

MOD := 1000000007

// Find max height
h := 0
while (h + 1) × (h + 2) / 2 <= r + g
    h := h + 1
S := h × (h + 1) / 2

// DP with space optimization (1D array)
dp := array of size S + 1, all set to 0
dp[0] := 1

for i from 1 to h
    for j from S down to i
        dp[j] := (dp[j] + dp[j - i]) mod MOD

// Sum valid states
answer := 0
for j from 0 to S
    if j <= r and S - j <= g then
        answer := (answer + dp[j]) mod MOD
return answer

The $1$D array trick works because level $i$ adds $i$ blocks. Processing $j$ from $S$ down to $i$ prevents counting the same level twice. This is the same reverse-loop pattern from 0/1 knapsack. After all $h$ levels, dp[j] holds the number of ways to use exactly $j$ red blocks across the full tower. You sum only the entries where both constraints ($j \le r$ and $S - j \le g$) are satisfied.

Time complexity: $O(h \cdot S)$.

Space complexity: $O(S)$ where $S = \frac{h(h+1)}{2}$.