Submission #73539544

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;
int T;
int n, kk, l;
int a[200005];
priority_queue<int> q;
void solve()
{
    cin >> n >> kk >> l;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    int bg = a[1], ed = l - a[n], ans = 0, temp = 0;
    for (int i = 2; i <= n; i++)
        q.push((a[i] - a[i - 1]) / 2);
    // cout << kk << '\n';
    ans = max(bg, ed) + (kk - 1) * (bg + ed);
    for (int i = 1; i <= kk; i++)
    {
        if (q.empty())
            break;
        temp += q.top();
        bg += q.top(), ed += q.top(), q.pop();
        // cout << bg << '|' << ed << '|' << temp << '\n';
        ans = max(temp + (kk - i <= 0 ? 0 : max(bg, ed)) + (kk - i - 1 <= 0 ? 0 : (kk - i - 1) * (bg + ed)), ans);
    }
    while (!q.empty())
        q.pop();
    for (int i = 1; i <= n; i++)
        a[i] = 0;
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
        solve();
}

Submission Info

Judge Result