题面展示

你有三个长度为 $n$ 的数组 $D$、$L$ 和 $R$，下标从 $1$ 开始。同时给定整数 $a_{0}$ 和 $b_{0}$。你需要按如下规则构造两个长度为 $n+1$ 的数组 $A$ 和 $B$：

• $A_{0} = a_{0}$，$B_{0} = b_{0}$。
• 对于所有 $1 \leq i \leq n$，依次进行以下操作：
  • 令 $A_{i} = A_{i-1} + D_{i}$，$B_{i} = B_{i-1} + D_{i}$。
  • 然后恰好选择以下两种操作中的一种并应用：
    • $A_{i} = \min(A_{i}, L_{i})$
    • $B_{i} = \min(B_{i}, R_{i})$

你希望通过上述操作，构造出 $A$ 和 $B$，使 $A_{n} + B_{n}$ 的值最大。请你求出能够得到的 $A_{n} + B_{n}$ 的最大值。

解题思路

由于我们只关心 $A_{n}$，而 $L_i$ 对 $A_i$ 做限制，因此考虑转而让 $L_i$ 限制 $A_n$。

求出 $D$ 的前缀和数组 $S_i$，令 $Ln_i = L_i + D_n - D_i$. 这样就有 $A_n = \min_{i=1}^{n}[\text{选择让 i 位置限制 A}]Ln_i$。

类似地，令 $Rn_i = R_i + D_n - D_i$。这样就有 $B_n = \min_{i=1}^{n}[\text{选择让 i 位置限制 B}]Rn_i$。

把 ${Ln_i,Rn_i}$ 存成一个 pair<int,int>，然后按 $Ln_i$ 从小到大排序。

• 选择限制 $A$ 的下标是排序后的一段后缀。

你已经限制 $Ln_i$ 了，假如 $Ln_j > Ln_i$，那么限制 $Ln_j$ 而非 $Rn_j$ 一定不劣。

如果是这样，直接扫一遍“这个后缀的左端点”就出结果了。

代码展示

#include<bits/stdc++.h>
#define int long long
#define l first
#define r second
using namespace std;
int n,k,d[1000005],a,b;
pair<int,int>s[1000005];
bool cmp(pair<int,int> x,pair<int,int> y){
    return x.r<y.r;
}
void solve(){
    cin>>n;
    for (int i=1;i<=n;i++)cin>>d[i],d[i]+=d[i-1];
    for (int i=1;i<=n;i++){
        cin>>s[i].l;
        s[i].l+=d[n]-d[i];
    }
    for (int i=1;i<=n;i++){
        cin>>s[i].r;
        s[i].r+=d[n]-d[i];
    }
    cin>>s[0].l>>s[0].r;
    s[0].l+=d[n],s[0].r+=d[n];
    sort(s+1,s+1+n);
    int x=s[0].r,ans=s[0].r;
    for (int i=1;i<=n;i++){
        if (s[i].l<s[0].l)ans=min(ans,s[i].r);
    }
    ans+=s[0].l;
    for (int i=1;i<=n;i++){
        if (s[i].l<=s[0].l){
            ans=max(ans,x+s[i].l);
            x=min(x,s[i].r);
        }
        else break;
    }
    cout<<ans<<"\n";
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    while (t--)solve();
    return 0;
}