不难看出题目需要分类讨论后两组赠品是最大还是次大即 2 \times 1=2 种，我们以第一种为例子（假设第一组赠品价值最小、第二组赠品次小、第三组赠品最大）。我们设数组断点为 i,j（1 \le i \le j \le n），设 a 中前 i 个元素的和为 p_i，容易的出：
根据上述分析以及结合数据范围，我们可以想到，对于第一种情况，枚举第一个断点 $i$，并且二分找到符合最左的符合 $\max(2p_i,\frac{p_n-p_i-m}{2}) \le p_j \le \min(m+2p_i,\frac{p_n-p_i}{2})$ 的 $j$，并更新答案这样肯定是对的（因为前缀和单调递增所以是可以二分的）。
对于剩下的 $1$ 种情况也可以用类似的方法求解，时间复杂度为 $O(n \log n)$，可以通过。
### 代码
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int a[N];
vector<int>p;
int ceildiv2(int A){
return (A>=0)?((A+1)/2):(A/2);
}
int floordiv2(int A){
return (A>=0)?(A/2):((A-1)/2);
}
signed main(){
int n,m,c,k;
cin>>n>>m>>c>>k;
int sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(k>3*c){
cout<<"-1\n";
return 0;
}
int t3=min(c,k);
int rem=k-t3;
int t2=min(c,rem);
int t1=k-t3-t2;
p.push_back(0);
for(int i=1;i<=n;i++){
p.push_back(p[i-1]+a[i]);
}
int ans=-1;
//先枚举第一个断点i
//方案1：A<=B<=C
for(int i=0;i<=n;i++){
int L=max(2*p[i],ceildiv2(p[i]+p[n]-m));
int R=min(m+2*p[i],floordiv2(p[i]+p[n]));
if(L>R)continue;
auto it=lower_bound(p.begin()+i,p.end(),L);
if(it!=p.end() && (*it)<=R){
int pj=*it;
int cur=t1*p[i]+t2*(pj-p[i])+t3*(p[n]-pj);
ans=max(ans,cur);
}
}
//方案2：A<=C<=B
for(int i=0;i<=n;i++){
int L=max(ceildiv2(p[n]+p[i]),p[n]-p[i]-m);
int R=min(floordiv2(p[n]+p[i]+m),p[n]-p[i]);
if(L>R)continue;
auto it=upper_bound(p.begin()+i,p.end(),R);
if(it!=p.begin()+i){
it--;
int pj=*it;
if(pj>=L){
int cur=t1*p[i]+t3*(pj-p[i])+t2*(p[n]-pj);
ans=max(ans,cur);
}
}
}
return 0;
}
```