题目大意

删除最少数，使得数组最大子段和小于 $S$ 。

分析

$S<0$ 显然只统计小于 $S$ 的数的个数。

最大子段和是可以根据 $f_i=\max (f_{i-1},0)+1$ 达到 $\mathcal{O}(n)$ 扫的。尽量避免带修等问题，就考虑一边扫一边微调：当扫到正数时，当前最大子段和是否大于等于 $S$ ，是则删除若干最大值；当扫到负数时，需要若干个最小值与之抵消。

代码

const int N = 1e6 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

int n, ans;
ll m, sum;
ll a[N];
multiset<ll> t;
bool vis[N];

int main() {
//	freopen("11.in", "r", stdin);
//	freopen("1.out", "w", stdout);
	n = Read(), m = Read();
	for (int i = 1; i <= n; i++) a[i] = Read();
	if (m < 0) {
		for (int i = 1; i <= n; i++) 
			if (a[i] >= m) ans++;
		printf ("%d\n", ans);
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		if (a[i] > 0) {
			t.insert(a[i]);
			sum += a[i];
			while (sum >= m) {
				multiset<ll>::iterator mx = t.lower_bound(1ll << 60);
				mx--;
				sum -= *mx;
				ans++;
				t.erase(mx);
			}
		} else {
			for (ll val = 0ll; t.size() && val < -a[i]; ) {
				multiset<ll>::iterator mn = t.upper_bound(0ll);
				sum -= *mn;
				val += *mn;
				t.erase(mn);
				if (val >= -a[i]) {
					t.insert(val + a[i]), sum += val + a[i];
					break;
				}
			}
		}
	}
	printf ("%d\n", ans);
	return 0;
}