By Lindsey L. (11th Grade)
https://codeforces.com/contest/2173/problem/B 12/13/25
Concepts: greedy
Observations
- Should choose larger k to maximize k – ai (red card)
- Choose smaller k to maximize bi – k (blue card)
Solution:
store the max and min score at each position.
At each position i:
min[i] = min(b[i] – max[i – 1], min[i – 1] – a[i])
max[i] = max(b[i] – min[i – 1], max[i – 1] – a[i]);
The answer will be max[n – 1].
