Nine Point Eight

InfiniteRobin · 2026-05-12 17:12:35 · 题解

细节题。

思路

首先求前缀和。

考虑枚举 S_1。

在确定 S_1 后，接下来只需要确定 S_2 和 S_3 的分界。

由于贪心，在 S_1 的值确定的情况下，我们使 S_3 的值尽可能大是一定优的，因为买 S_3 的人数一定不少于买 S_2 的人数。

那么我们分类讨论，确定中间一块是 S_2 还是 S_3。

然后把所有限制都转为前缀和形式，之后通过二分限定满足条件的下标区间即可。结合上面贪心结论，最值一定在区间边界取到。

代码

:::success[AC Code]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

ll n, m, c, k;
ll a[N], pre[N];

bool check(int i, int j){
    if(i > j) return 0;
    ll s1 = pre[i], s2 = pre[j] - pre[i], s3 = pre[n] - pre[j];
    if(min(s2, s3) - s1 <= m && max(s2, s3) - min(s2, s3) <= m && s1 <= min(s2, s3)) return 1;
    return 0;
}

ll inline F(int i, int j){
    if(!check(i, j)) return -1;
    ll w = min(c, k) * (pre[n] - pre[j]) + max(min(k - c, c), 0ll) * (pre[j] - pre[i]) + max(k - 2 * c, 0ll) * pre[i];
    return w;
}
ll inline F2(int i, int j){
    if(!check(i, j)) return -1;
    ll w = max(min(k - c, c), 0ll) * (pre[n] - pre[j]) + min(c, k) * (pre[j] - pre[i]) + max(k - 2 * c, 0ll) * pre[i];
    return w;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin >>n>>m>>c>>k;
    for(int i = 1; i <= n; i ++){
        cin >>a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    if(3 * c < k){
        cout <<"-1";
        return 0;
    }

    ll ans = -1;
    for(int i = 0; i <= n; i ++){
        int p = lower_bound(pre, pre + 1 + n, 2 * pre[i]) - pre;

        if(pre[p] - pre[i] <= pre[n] - pre[p]){
            if(pre[n] - pre[p] - (pre[p] - pre[i]) > m){
                int p2 = lower_bound(pre, pre + 1 + n, (pre[i] + pre[n] - m) / 2) - pre;
                if(pre[p2] - 2 * pre[i] <= m) ans = max(ans, F(i, p2));
            }
            else if(pre[p] - 2 * pre[i] <= m) ans = max(ans, F(i, p));
        }

        ll maxn = min((m + pre[i] + pre[n]) / 2, pre[n] - pre[i]);
        int p2 = upper_bound(pre, pre + 1 + n, maxn) - pre - 1;
        if(p2 < p) continue;
        if(pre[n] - pre[p2] - pre[i] <= m) ans = max(ans, F2(i, p2));
    }
    cout <<ans;

    return 0;
}

:::