P3594 [POI2015]WIL-Wilcze doły

POI 合集。

考虑实时维护对于当前 $[l,r]$ 所有连续 $p$ 个数的和的最大值，前缀和 + 双指针 + 单调队列优化即可。

$r\to r+1$ 时往单调队列加入 $\sum_{i=r-p+2}^{r+1} a_i$，不满足条件令 $l\to l+1$ 时若单调队列队首是 $\sum_{i=l}^{l+p-1}a_i$ 则弹出。时间复杂度线性。

const int N = 2e6 + 5;
int n, len, ans, hd = 1, tl, d[N];
ll w[N], p, val[N];
int main(){
	cin >> n >> p >> len;
	for(int i = 1; i <= n; i++) w[i] = read() + w[i - 1];
	for(int l = 1, r = len; r <= n; r++) {
		ll sum = w[r] - w[r - len];
		while(hd <= tl && sum >= val[tl]) tl--;
		d[++tl] = r, val[tl] = sum;
		while(w[r] - w[l - 1] - val[hd] > p) {if(d[hd] == l + len - 1) hd++; l++;}
		if(r - l + 1 > ans) ans = r - l + 1;
	} cout << ans << endl;
	return 0;
}