Submission #74943546

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ft first
#define sd second
using namespace std;
using namespace __gnu_pbds;
using bs = bitset<8000>;
const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int M = 2005;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const char dir[4] = {'U', 'D', 'L', 'R'};

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> d(n);
    for (int i = 0; i < n; ++i) cin >> d[i];
    sort(d.begin(), d.end());
    vector<ll> pref(n + 1, 0);
    for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + d[i];
    auto calc = [&](ll L) -> ll {
        ll R = L + k - 1;
        int l = lower_bound(d.begin(), d.end(), L) - d.begin();    
        int r = upper_bound(d.begin(), d.end(), R) - d.begin() - 1;
        ll ct = 0;
        if (l > 0) {
            ct += L * l - pref[l];
        }
        if (r < n - 1) {
            ct += (pref[n] - pref[r + 1]) - R * (n - 1 - r);
        }
        return ct;
    };
    ll ans = LLONG_MAX;
    for (int i = 0; i < n; ++i) {
        ans = min(ans, calc(d[i]));
        ans = min(ans, calc(d[i] - k + 1));
    }
    cout << ans << '\n';
    return 0;
}

Submission Info

Judge Result