Niko's Tactical Cards

We need maximize the final score after $n$ forced choices. On turn $i$, from a current score $k$:

• red gives $k-a_i$
• blue gives $b_i-k$

The obvious brute force has $2^n$ strategies, which is impressively dead on arrival. So we need to compress the reachable scores.

Key Observation

At any turn, we do not need every reachable score. We only need the current maximum and minimum reachable scores.

Why?

For a fixed turn $i$:

• Red: $k-a_i$ increases when $k$ increases. So the best red result comes from the previous maximum score.

• Blue: $b_i-k$ decreases when $k$ increases. So the best blue result comes from the previous minimum score.

That means the next maximum is determined only by the previous maximum and previous minimum:

$$mx' = \max(mx-a_i,\ b_i-mn)$$

But we also need the next minimum, because a terrible score can become amazing later through a blue card. That is the whole trick; negative scores are not trash, they are just potential slingshots.

For the minimum:

• Red minimum comes from previous minimum: $mn-a_i$
• Blue minimum comes from previous maximum: $b_i-mx$

So:

$$mn' = \min(mn-a_i,\ b_i-mx)$$

Initialization

Before any turns, the only reachable score is $0$, so:

$$mx = mn = 0$$

Then process each pair $(a_i,b_i)$ and update both values at the same time. Do not update $mx$ first and then use the new value for $mn$; that would mix turns and create fake strategies. Store the new values separately.

Why this is enough

Suppose after some turn the set of reachable scores is huge. For the next turn, every possible next score is created by one of these two functions:

$$f(k)=k-a_i$$ $$g(k)=b_i-k$$

Function $f$ is increasing, so its maximum and minimum over all reachable $k$ happen at the old maximum and old minimum.

Function $g$ is decreasing, so its maximum and minimum happen at the old minimum and old maximum.

Therefore, knowing only $(mn,mx)$ preserves exactly the information needed for all future extrema. No hidden middle value can suddenly beat both endpoints, because these functions are linear and monotonic. Middle values can sit down.

Algorithm

For each test case:

1. Read $n$, arrays $a$ and $b$.
2. Set $mn=mx=0$.
3. For each $i$ from $0$ to $n-1$:
   • $newMx=\max(mx-a_i, b_i-mn)$
   • $newMn=\min(mn-a_i, b_i-mx)$
   • assign $mx=newMx$, $mn=newMn$
4. Print $mx$.

Complexity

Each turn is processed once.

Time complexity:

$$O(n)$$

per test case.

Memory complexity:

$$O(n)$$

if storing both arrays, though the DP itself is $O(1)$. With the given input format, storing arrays is clean and totally fine.

Values can reach around $10^{14}$, so use long long. int would explode and then gaslight you with wrong answers.