Programmers

input/code.cpp: In function 'int main()':
input/code.cpp:62:10: warning: unused variable 'b' [-Wunused-variable]
     ll a,b,c,d;
          ^
input/code.cpp:62:12: warning: unused variable 'c' [-Wunused-variable]
     ll a,b,c,d;
            ^
input/code.cpp:62:14: warning: unused variable 'd' [-Wunused-variable]
     ll a,b,c,d;
              ^

#pragma GCC optimize("O3")   //
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, b, a) for(int i = b - 1; i >= a; i--)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;
typedef unsigned long long ull;

unsigned seed = chrono::system_clock::now().time_since_epoch().count();
mt19937 eng(seed);

ll random2(){
    return (1ll << 31ll)*eng()+eng();
}

ll n,m,k,q,T;

const ll big = 1000000007;
const ll big2 = 1000000009;
const ll mod =  998244353;

const int MAXN = 200002;

vl X,A;

double DP1[MAXN];
int DP2[MAXN];
int DPC[MAXN] = {0};
int cc = 0;
double alien = 0.0;

pair<double, int> dp(int i){
    if(i >= n)return {0, 0};
    if(DPC[i] == cc)return {DP1[i], DP2[i]};
    pair<double, int> temp1 = dp(i+1);
    pair<double, int> temp2 = dp(i+2);
    temp2.second++;
    temp2.first += X[i]-alien;
    pair<double, int> ans = min(temp1, temp2);
    DPC[i] = cc;
    DP1[i] = ans.first;
    DP2[i] = ans.second;
    return ans;
}

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

    //freopen("fhc.txt","r",stdin);
    //freopen("autput.txt","w",stdout);

    ll a,b,c,d;

    cin >> n >> k;

    rep(c1,0,n){
        cin >> a;
        A.push_back(a);
    }
    sort(all(A));
    rep(c1,0,n-1){
        X.push_back(A[c1+1]-A[c1]);
    }
    n--;

    double L = 0.0;
    double R = big;

    rep(c1,0,200){
        double mid = (L+R)/2.0;
        alien = mid;
        cc++;
        pair<double, int> res = dp(0);
        if(res.second < k){
            L = mid;
        }
        if(res.second > k){
            R = mid;
        }
        if(res.second == k){
            double ans = res.first + k*alien;
           // cerr << "FOUND IT\n";
            cout << round(ans) << "\n";
            return 0;
        }
    }

    alien = L;
    pair<double, int> res = dp(0);
    double ans = res.first + k*alien;
    cout << round(ans) << "\n";

    return 0;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

Test 11

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 12

Group: 1, 3

Verdict: WRONG ANSWER

Test 13

Group: 1, 3

Verdict: WRONG ANSWER

Test 14

Group: 1, 3

Verdict: WRONG ANSWER

Test 15

Group: 1, 3

Verdict: WRONG ANSWER

Test 16

Group: 1, 3

Verdict: WRONG ANSWER

Test 17

Group: 2, 3

Verdict: WRONG ANSWER

Test 18

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 2, 3

Verdict: ACCEPTED

Test 21

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 2, 3

Verdict: ACCEPTED

Test 23

Group: 2, 3

Verdict: ACCEPTED

Test 24

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 3

Verdict: WRONG ANSWER

Test 27

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 28

Group: 3

Verdict: WRONG ANSWER

Test 29

Group: 3

Verdict: WRONG ANSWER

Test 30

Group: 3

Verdict: WRONG ANSWER

Test 31

Group: 3

Verdict: WRONG ANSWER