题目描述

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

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

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

Examples
input

10 5
0 1 0 2 0 -3 0 -4 0 -5

output

3

input

3 1
1 -1 0

output

0

input

9 3
0 0 1 0 2 -3 -2 -2 1

output

4

思路

$m$小于等于$5000$，基本可以知道这是一道dp题
考虑到出现的正负数只能被更之前的0处分配点数，可以在0出现的时候计算分配的结果
开两个差分数组分别存正负数的贡献
用$dp[i]$表示分配了$i$个点给正数后的最大通过次数
$$dp[i]+=a[i]+b[p-i]$$
值得注意的是，每一次更新完dp数组后，需要将差分数组清零，因为后面的点数不能对前面的产生影响
而dp数组需要倒序更新：每一步只能由前一步推出，而不能从头往后推
具体可以把弄一下这组数据

9 4
2 -1 0  0 -2 3 0 3 0

1

当$j==p$时，此时是加了一点属性，但还没具体分配，所以直接等于$dp[j-1]$

对于任意其他$j$来说，是从这p-1个属性点中选j个加给正数

如果对于前一个点多出来的属性点给正数，那么此时的正数比上一个点多1，$$dp[j] = dp[j - 1]$$
如果对于前一个点多出来的属性点给负数，那么此时正数和上一个点一样多，$$dp[j] = dp[j]$$
而我们只需要取其中最大的即可

$O(m^2 + n)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> dp(m + 2), a(m + 1), b(m + 1);
  int p = 0;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x > 0) {
      a[x]++;
    } else if (x < 0) {
      b[-x]++;
    }
    if (x == 0 || i == n - 1) {
      for (int j = 1; j <= p; j++) {
        a[j] = a[j] + a[j - 1];
        b[j] = b[j] + b[j - 1];
      }
      for (int j = 0; j <= p; j++) {
        dp[j] = dp[j] + a[j] + b[p - j];
      }
      p++;
      for (int j = p; j; j--) {
        dp[j] = max(dp[j], dp[j - 1]);
      }
      fill(a.begin(), a.end(), 0);
      fill(b.begin(), b.end(), 0);
    }
  }

  int ans = 0;
  for (int i = 0; i <= m; i++) {
    ans = max(ans, dp[i]);
  }
  cout << ans << "\n";
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int _ = 1;
  while (_--) {
    solve();
  }
  return 0;
}