思路

题目要把零食分成三段（每段非空），分别用三种吃法，最大化总满足度。对每个合法划分 $1\le x<y<N$，总满足度为

$$\sum_{i=1}^{x}A_i+\sum_{i=x+1}^{y}B_i+\sum_{i=y+1}^{N}C_i$$

把第二段和第三段改写成前缀和的形式：

$$\sum_{i=1}^{x}(A_i-B_i)+\sum_{i=1}^{y}B_i+\sum_{i=y+1}^{N}C_i$$

记 $PA,PB,PC$ 为 $A,B,C$ 的前缀和，则总满足度为

$$(PA_x-PB_x)+\left(PB_y+PC_N-PC_y\right)$$

枚举 $x$ 时，括号内只与 $y$ 有关，因此先对每个 $y$ 预处理后缀最大值

$$best[i]=\max_{y\ge i}\left(PB_y+PC_N-PC_y\right)$$

答案即

$$\max_{1\le x\le N-2}\left(PA_x-PB_x+best[x+1]\right)$$

注意 $x$ 只能取到 $N-2$、$y$ 只能取到 $N-1$，保证三段都非空；实现时循环上界取 $N-2$，后缀最大值也从 $N-1$ 开始算，不要把 $y=N$ 这样的非法候选算进来。

时间复杂度 $O(N)$，空间复杂度 $O(N)$。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

void go(){
    int n;cin>>n;
    vector<int>a(n+1,0), b(n+1,0), c(n+1,0);
    vector<int>fa(n+2,0), fb(n+2,0), fc(n+2,0), d(n+2, 0);// 前缀和数组与后缀最大值数组

    // 读入并计算三组数据的前缀和
    for(int i=1;i<=n;i++){cin>>a[i]; fa[i] = fa[i-1]+a[i];}
    for(int i=1;i<=n;i++){cin>>b[i]; fb[i] = fb[i-1]+b[i];}
    for(int i=1;i<=n;i++){cin>>c[i]; fc[i] = fc[i-1]+c[i];}

    // 从后往前预处理：d[i] = max_{y>=i} (fb[y] + fc[n] - fc[y])
    for(int i=n-1;i>=1;i--){          // y 最大只能取 n-1，保证第三段非空
        d[i] = max(d[i+1], fb[i]+fc[n]-fc[i]);
    }

    int ans = 0;
    // 枚举第一段的右端点 x，配合 y 的后缀最大值
    for(int i=1;i<=n-2;i++){          // x 最大只能取 n-2，保证后两段非空
        ans = max(ans, fa[i]-fb[i] + d[i+1]);
    }

    cout<<ans<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _=1;
    // 本题只有一组数据，不需要读入测试组数
    while(_--){
        go();
    }
    return 0;
}