- Translate each rule into one explicit state update.
- Maintain the invariant after every processed item.
- Return the accumulated state once all relevant input has been handled.
Code notes
- 67 lines of Python from the credited upstream file arc197_a.py.
- The implementation visibly relies on sequence storage, ordered lookup.
- No explicit loop blocks detected.
Complexity
Count the number and nesting of passes over the input, then include the maintained containers in the memory estimate.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4def solve():5 h, w = map(int, input().split())6 s = list(input().rstrip())7 8 d_count = s.count("D")9 r_count = s.count("R")10 d = ["D"] * (h - 1 - d_count)11 r = ["R"] * (w - 1 - r_count)12 dr, rd = d + r, r + d13 x1, y1 = 0, 014 x2, y2 = 0, 015 y_min = [h - 1] * w16 y_max = [0] * w17 y_min[0] = y_max[0] = 018 19 for i, si in enumerate(s):20 if si == "D":21 y1 += 122 y2 += 123 elif si == "R":24 x1 += 125 x2 += 126 else:27 rdi = rd.pop()28 dri = dr.pop()29 30 if rdi == "D":31 y1 += 132 else:33 x1 += 134 35 if dri == "D":36 y2 += 137 else:38 x2 += 139 40 y_min[x1] = min(y_min[x1], y1)41 y_min[x2] = min(y_min[x2], y2)42 43 y_max[x1] = max(y_max[x1], y1)44 y_max[x2] = max(y_max[x2], y2)45 46 ans = 047 48 for y_min_i, y_max_i in zip(y_min, y_max):49 ans += y_max_i - y_min_i + 150 51 print(ans)52 53 54def main():55 import sys56 57 input = sys.stdin.readline58 59 t = int(input())60 61 for _ in range(t):62 solve()63 64 65if __name__ == "__main__":66 main()67