记录编号	618156	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	果蝇诱饵	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	1.380 s
提交时间	2026-08-27 14:57:11	内存使用	9.06 MiB

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

using ll = long long;
const int N = 2 * 1e5 + 5;
int n;
ll k, l;

struct seq{
    ll l, r;
    ll v;
    bool operator<(const seq &o)const{
        return v > o.v;
    }
}s[N];
ll p[N];
ll sum[N];
ll hp1[N], hpn[N];

inline void solve(){
    cin >> n >> k >> l;
    for(int i = 1;i <= n;i ++){
        cin >> p[i];
    }
    sort(p + 1, p + n + 1);
    ll p1 = p[1], pn = p[n];
    ll tot = 0;
    for(int i = 1;i < n;i ++){
        ll l = p[i], r = p[i + 1];
        ll v = r - l + 1;
        s[++ tot] = {l, r, v};
    }
    sort(s + 1, s + tot + 1);
//    for(int i = 1;i <= tot;i ++){
//        cout << s[i].l << ' ' << s[i].r << ' ' << s[i].v << '\n';
//    }
    hp1[0] = p1, hpn[0] = pn;
    for(int i = 1;i <= tot;i ++){
        ll mid = (s[i].r + s[i].l) >> 1;
        ll delta = s[i].r - mid;
//        cout << "MID & DELTA\n";
//        cout << mid << '\n';
//        cout << delta << '\n';
        hp1[i] = hp1[i - 1] + delta;
        hpn[i] = hpn[i - 1] - delta;
        sum[i] = sum[i - 1] + delta;
    }
    ll ans = 0;
    for(ll i = 0;i <= min(k, tot);i ++){
//        cout << "i : " << i << '\n';
        ll pit = k - i;
        ll np1 = hp1[i], npn = hpn[i];
//        cout << "1 & n :: " << np1 << ' ' << npn << '\n';
        ll mx = max(np1, l - npn);
//        cout << "mx1 + mx2 : " << np1 + (l - npn) << '\n';
        ll cnt = 0;
        if(pit == 1){
            cnt += pit * mx;
        }
        else if(pit >= 2){
            cnt += mx;
            cnt += (pit - 1) * (np1 + (l - npn));
        }
//        cout << "sum[i] : " << sum[i] << '\n';
//        cout << "point : " << cnt << '\n';
        cnt += sum[i];
        ans = max(ans, cnt);
    }
    cout << ans << '\n';
}

int main(){
    freopen("fly.in", "r", stdin);
    freopen("fly.out", "w", stdout);
    cin.tie(0) -> ios::sync_with_stdio(0);
    int T; cin >> T;
    while(T --) solve();
    return 0;
}