Attribute Checks
Contest: Educational Codeforces Round 170 (Rated for Div. 2)
Difficulty rating: 1800
Tags: brute force, data structures, dp, implementation, math, two pointers

Imagine a game where you play as a character that has two attributes: "Strength" and "Intelligence", that are at zero level initially.

During the game, you'll acquire $$$m$$$ attribute points that allow you to increase your attribute levels — one point will increase one of the attributes by one level. But sometimes, you'll encounter a so-called "Attribute Checks": if your corresponding attribute is high enough, you'll pass it; otherwise, you'll fail it.

Spending some time, you finally prepared a list which contains records of all points you got and all checks you've met. And now you're wondering: what is the maximum number of attribute checks you can pass in a single run if you'd spend points wisely?

Note that you can't change the order of records.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le m \le 5000$$$; $$$m < n \le 2 \cdot 10^6$$$) — the number of records in the list and the total number of points you'll get during the game.

The second line contains $$$n$$$ integers $$$r_1, r_2, \dots, r_n$$$ ($$$-m \le r_i \le m$$$), where $$$r_i$$$ encodes the $$$i$$$-th record:

- If $$$r_i = 0$$$, then the $$$i$$$-th record is an acquiring one attribute point. You can spend to level up either Strength or Intelligence;
- If $$$r_i > 0$$$, then it's an Intelligence check: if your Intelligence level is greater than or equal to $$$|r_i|$$$, you pass.
- If $$$r_i < 0$$$, then it's a Strength check: if your Strength level is greater than or equal to $$$|r_i|$$$, you pass.

Additional constraint on the input: the sequence $$$r_1, r_2, \dots, r_n$$$ contains exactly $$$m$$$ elements equal to $$$0$$$.

Output format:
Print one integer — the maximum number of checks you can pass.

Constraints:
Time limit: 2.5 s
Memory limit: 512.0 MB

Note:
In the first test, it's optimal to spend each point in Strength, so you'll fail $$$2$$$ Intelligence checks but pass $$$3$$$ Strength checks.

In the second test, you'll fail both checks, since the first point you get comes after the checks.

In the third test, one of the optimal strategies is:

1. spend the first point on Intelligence;
2. spend the second point on Strength;
3. spend the third point on Strength;

Example input:
10 5
0 1 0 2 0 -3 0 -4 0 -5

Example output:
3

Example input:
3 1
1 -1 0

Example output:
0

Editorial:
For the start, let's introduce a slow but correct solution. Let $$$d[i][I]$$$ be the answer to the task if we processed first $$$i$$$ records and the current Intelligence level is $$$I$$$. If we know Intelligence level $$$I$$$, then we also know the current Strength level $$$S = P - I$$$, where $$$P$$$ is just a total number of points in first $$$i$$$ records.
Since we want to use dp, let's discuss transitions:
• If the last record $$$r_i = 0$$$, then it was a point, and there are only two options:   we either raised Intelligence, so the last state was $$$d[i - 1][I - 1]$$$;  or raised Strength, coming from state $$$d[i - 1][I]$$$.  In other words, we can calculate $$$d[i][I] = \max(d[i - 1][I - 1], d[i - 1][I])$$$.
• we either raised Intelligence, so the last state was $$$d[i - 1][I - 1]$$$;
• or raised Strength, coming from state $$$d[i - 1][I]$$$.
• If the last record $$$r_i > 0$$$, then it's an Intelligence check, and it doesn't affect the state, only its answer. For all $$$I \ge r_i$$$, $$$d[i][I] = d[i - 1][I] + 1$$$; otherwise, it's $$$d[i][I] = d[i - 1][I]$$$.
• If $$$r_i < 0$$$, then it's a Strength check and affects the values in a similar way. For all $$$I \le P + r_i$$$, $$$d[i][I] = d[i - 1][I] + 1$$$; otherwise, it's also $$$d[i][I] = d[i - 1][I]$$$.
OK, we've got a solution with $$$O(nm)$$$ time and memory, but we can speed it up. Note that the first case appears only $$$O(m)$$$ times, while the second and third cases are just range additions. So, if we can do addition in $$$O(1)$$$, then processing the first case in linear time is enough to achieve $$$O(m^2 + n)$$$ complexity.
How to process range additions in $$$O(1)$$$ time? Let's use some difference array $$$a$$$ to do it lazily. Instead of adding some value $$$v$$$ to the segment $$$[l, r]$$$, we'll only add value $$$v$$$ to $$$a[l]$$$ and $$$-v$$$ to $$$a[r + 1]$$$. And when we meet $$$r_i = 0$$$, we'll "push" all accumulated operations all at once.
The total value you need to add to some position $$$i$$$ is $$$\sum_{j=0}^{i}{a[i]}$$$. So, we can calculate all of them in $$$O(m)$$$ just going from left to right, maintaining the prefix sum.
The last question is reducing the space complexity. As usual, you can store only the last two layers: for the current layer $$$i$$$ and previous layer $$$i - 1$$$. But actually, you can store only one layer and update it in-place.
Let's store only one last layer of dp as $$$d[I]$$$. Attribute checks don't change array $$$d$$$ at all. In case $$$r_i = 0$$$, you, firstly, push all data from $$$a$$$ to $$$d$$$, and then you need to recalc values in $$$d$$$. But since the formula is $$$d[I] = \max(d[I], d[I - 1])$$$, you can just iterate over $$$I$$$ in descending order and everything works!
In total, we have a solution with $$$O(m^2 + n)$$$ time and $$$O(m)$$$ space complexity.