E-可口蛋糕

若给定区间左端点，在饱腹值之和大于等于的情况下，可口值之和越大越优

考虑按饱腹值之和由小到大、可口值之和由大到小维护一个单调队列，枚举区间左端点为到时的最优的可口值之和，枚举过程可以维护一个和分别表示在左端点为的基础上饱腹值之和与可口值之和应减去多少

时间复杂度：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using l2 = array<ll, 2>;

const int N = 1e6 + 10;
ll w[N], d[N];
l2 q[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++ i) cin >> w[i];
	for (int i = 1; i <= n; ++ i) cin >> d[i];

	int front = 0, rear = -1;
	ll prew = 0, pred = 0;
	for (int i = 1; i <= n; ++ i) {
		prew += w[i], pred += d[i];
		if (prew < m) continue;
		while (front <= rear && q[rear][1] <= pred) -- rear;
		++ rear;
		q[rear][0] = prew, q[rear][1] = pred;
	}

	ll t1 = 0, t2 = 0, ans = q[front][1];
	for (int i = 1; i <= n; ++ i) {
		t1 -= w[i], t2 -= d[i];
		while (front <= rear && q[front][0] + t1 < m) ++ front;
		if (front <= rear) ans = max(ans, q[front][1] + t2);
	}
	cout << ans << '\n';

	return 0;
}