题意：

小明为了变得越来越神，他给自己制定了 nn 个任务，编号为 1,2,⋅⋅⋅,n1,2,···,n。小明在完成这些任务之前有一个初始兴奋值 mm，每个任务都有一个难度值 hard[i]hard[i],且对于任何 i>ji>j，有 hard[i]>hard[j]hard[i]>hard[j]，小明完成第 ii 个任务，兴奋值至少会减少 hard[i]hard[i]，第 ii 任务完成之后，小明会受到鼓舞，兴奋值又会增加 s[i]s[i]，每个任务只完成一次。小明可以一次完成所有剩余的难度值不超过现有兴奋度的任务，这样只会消耗那个最大的难度值。现在小明想知道完成这 nn 个任务之后，他的最大兴奋值为多少。

很明显的 DPDP 题。

设 f[i]f[i] 代表完成前 ii 个任务剩余的最大兴奋值，那么可以立即推出状态转移方程：

f[i]=max(f[i],f[j]−hard[i]+sum[i]−sum[j])(1≤j<i) f[i]=max(f[i],f[j]-hard[i]+sum[i]-sum[j])(1\leq j<i)

其中 sum[i]sum[i] 代表 s[i]s[i] 的前缀和。

由于对于每一个 ii，sum[i]sum[i] 与 hard[i]hard[i] 为定值，暂不考虑。

由于要让兴奋值最大，而 sum[i]sum[i] 和 hard[i]hard[i] 是定值，所以我们要让 f[j]−sum[j]f[j]-sum[j] 尽可能大，要找这个数的最大值，我们分析其是否具有单调性。

设 j<k<ij<k<i，其中 jj 和 kk 都由 ll 转移而来，可得：

f[j]=f[l]−hard[j]+sum[j]−sum[l],f[j]−sum[j]=f[l]−sum[l]−hard[j] f[j]=f[l]-hard[j]+sum[j]-sum[l],f[j]-sum[j]=f[l]-sum[l]-hard[j]
f[k]=f[l]−hard[k]+sum[k]−sum[l],f[k]−sum[k]=f[l]−sum[l]−hard[k] f[k]=f[l]-hard[k]+sum[k]-sum[l],f[k]-sum[k]=f[l]-sum[l]-hard[k]
(f[j]−sum[j])−(f[k]−sum[k])=hard[k]−hard[j]>0 (f[j]-sum[j])-(f[k]-sum[k])=hard[k]-hard[j]>0

由于 hardhard 数组单调递增，所以 hard[k]−hard[j]>0hard[k]-hard[j]>0。

所以 f[i]−sum[i]f[i]-sum[i] 单调递减，所以当在所有能转移到 ii 的 jj 中(前提条件，即 dp[j]>hard[i]dp[j]>hard[i]，否则兴奋值不够，无法完成第 ii 个任务)，取最小的那个 jj，能使答案最大。

所以我们可以用一个指针直接从左到右扫一遍即可，第一个满足前提条件的就是最小的。

问题解决，本质是用一个单调队列维护 f[i]−sum[i]f[i]-sum[i] 优化。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,hard[201010];
long long sum[201010],dp[201010];
int main()
{
	freopen("Plan.in","r",stdin);
	freopen("Plan.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&hard[i]);
	for(int i=1;i<=n;i++)
	{
		long long x;
		scanf("%lld",&x);
		sum[i]=sum[i-1]+x;
	}
	memset(dp,-0x3f,sizeof(dp));
	dp[0]=m;//初始化
	for(int i=1,j=0;i<=n;i++)
	{
		while(dp[j]<hard[i])
			j++;//类似的单调队列优化
		dp[i]=max(dp[i],dp[j]-hard[i]+sum[i]-sum[j]);//DP
	}
	printf("%lld",dp[n]);
	return 0;
}