Submission #73536241

---

Source Code Expand

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

int main(){
  ll T,N,K,L,l,r,ans;
  cin >> T;
  for(ll i = 0;i < T;i++){
    ans = 0;
    cin >> N >> K >> L;
    vector<ll> A(N),D(N - 1);
    for(ll j = 0;j < N;j++){
      cin >> A[j];
    }
    if(N == 1){
      cout << max(A[0],L - A[0]) + L * (K - 1) << endl;
      continue;
    }
    sort(A.begin(),A.end());
    l = A[0];
    r = A[N - 1];
    for(ll j = 0;j < N - 1;j++){
      D[j] = A[j + 1] - A[j];
    }
    sort(D.begin(),D.end());
    reverse(D.begin(),D.end());
    for(ll j = 0;j < min(N,K + 1);j++){
      ans = max(ans,l - A[0] + max(l,L - r) * min((ll)1,K - j) + (L - r + l) * max((ll)0,K - j - 1));
      if(j == N - 1){
        break;
      }
      l+=D[j] / 2;
      r-=D[j] / 2;
    }
    cout << ans << endl;
  }
}

Submission Info

Judge Result