CSES - Datatähti Open 2021 - Results
Submission details
Task:Programmers
Sender:endagorion
Submission time:2021-01-31 08:32:49 +0200
Language:C++17
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED34
#2ACCEPTED21
#3ACCEPTED45
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#8ACCEPTED0.01 s1, 2, 3details
#9ACCEPTED0.01 s1, 2, 3details
#10ACCEPTED0.01 s1, 2, 3details
#11ACCEPTED0.01 s1, 2, 3details
#12ACCEPTED0.01 s1, 3details
#13ACCEPTED0.01 s1, 3details
#14ACCEPTED0.01 s1, 3details
#15ACCEPTED0.01 s1, 3details
#16ACCEPTED0.01 s1, 3details
#17ACCEPTED0.04 s2, 3details
#18ACCEPTED0.11 s2, 3details
#19ACCEPTED0.10 s2, 3details
#20ACCEPTED0.12 s2, 3details
#21ACCEPTED0.12 s2, 3details
#22ACCEPTED0.12 s2, 3details
#23ACCEPTED0.12 s2, 3details
#24ACCEPTED0.35 s3details
#25ACCEPTED0.20 s3details
#26ACCEPTED0.38 s3details
#27ACCEPTED0.26 s3details
#28ACCEPTED0.37 s3details
#29ACCEPTED0.39 s3details
#30ACCEPTED0.39 s3details
#31ACCEPTED0.41 s3details

Code

#include <bits/stdc++.h>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = 210000;
int par[maxn], l[maxn], r[maxn];
i64 a[maxn], b[maxn], ps[maxn];

int root(int x) {
    return x == par[x] ? x : par[x] = root(par[x]);
}

i64 segs(int l, int r) {
    ++r;
    return ps[r] + ps[l] * ((r - l) % 2 == 0 ? -1 : 1);
}

void unite(int i, int j) {
    i = root(i);
    j = root(j);
    uin(l[i], l[j]);
    uax(r[i], r[j]);
    par[j] = i;
}

int L[maxn], R[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif
    
    int n, k;
    cin >> n >> k;
    forn(i, n) cin >> a[i];
    sort(a, a + n);

    b[0] = 1e18;
    forn(i, n - 1) b[i + 1] = a[i + 1] - a[i];
    b[n] = 1e18;
    set<pi64> q;
    forn(i, n + 1) {
        par[i] = i;
        l[i] = r[i] = i;
        q.insert(mp(b[i], i));
    }

    i64 ans = 0;
    forn(i, k) {
        auto ww = *q.begin();
        ans += ww.fi;
        q.erase(ww);
        int v = ww.se;
        assert(l[v] && r[v] < n);
        int u = root(l[v] - 1), w = root(r[v] + 1);
        q.erase(mp(b[u], u));
        q.erase(mp(b[w], w));
        b[v] = b[u] + b[w] - b[v];
        unite(v, u);
        unite(v, w);
        b[root(v)] = b[v];
        v = root(v);
        q.insert(mp(b[v], v));
    }

    cout << ans << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
8 3
3 1 2 7 9 3 4 7

correct output
1

user output
1

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
2 1
2 13

correct output
11

user output
11

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
20 10
16 20 6 15 19 12 11 17 20 6 15...

correct output
6

user output
6

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
14 5
11 3 8 3 14 8 10 13 11 10 17 1...

correct output
0

user output
0

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
15 1
8 5 1 8 18 15 6 20 14 9 10 9 1...

correct output
0

user output
0

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
10 3
10 19 16 15 12 5 14 8 3 15

correct output
4

user output
4

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
202 90
177 187 183 647 616 580 499 78...

correct output
213

user output
213

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
2000 512
141 583 135 833 900 308 248 58...

correct output
0

user output
0

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
2000 972
685 4 289 865 93 159 48 866 56...

correct output
276

user output
276

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
2000 1000
698 153 298 118 631 341 238 7 ...

correct output
517

user output
517

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

input
2000 1
983 144 449 584 839 166 77 885...

correct output
0

user output
0

Test 12

Group: 1, 3

Verdict: ACCEPTED

input
1464 320
846762124 954854396 12767390 7...

correct output
35809369

user output
35809369

Test 13

Group: 1, 3

Verdict: ACCEPTED

input
2000 231
801945178 924940258 369188694 ...

correct output
7831421

user output
7831421

Test 14

Group: 1, 3

Verdict: ACCEPTED

input
2000 461
464790475 932031556 838378103 ...

correct output
37272564

user output
37272564

Test 15

Group: 1, 3

Verdict: ACCEPTED

input
2000 100
484046702 267135814 995006323 ...

correct output
1268400

user output
1268400

Test 16

Group: 1, 3

Verdict: ACCEPTED

input
2000 996
98352148 438929491 242618159 1...

correct output
445965905

user output
445965905

Test 17

Group: 2, 3

Verdict: ACCEPTED

input
65879 19675
896 316 972 476 636 227 716 78...

correct output
0

user output
0

Test 18

Group: 2, 3

Verdict: ACCEPTED

input
200000 53820
995 720 135 767 943 742 191 26...

correct output
0

user output
0

Test 19

Group: 2, 3

Verdict: ACCEPTED

input
200000 32297
527 947 84 851 908 833 339 112...

correct output
0

user output
0

Test 20

Group: 2, 3

Verdict: ACCEPTED

input
200000 99982
561 174 242 275 460 109 664 68...

correct output
322

user output
322

Test 21

Group: 2, 3

Verdict: ACCEPTED

input
200000 99955
911 33 314 861 298 117 972 982...

correct output
245

user output
245

Test 22

Group: 2, 3

Verdict: ACCEPTED

input
200000 99972
783 1000 673 611 87 452 702 92...

correct output
290

user output
290

Test 23

Group: 2, 3

Verdict: ACCEPTED

input
200000 99961
795 136 128 643 60 422 371 839...

correct output
252

user output
252

Test 24

Group: 3

Verdict: ACCEPTED

input
195426 76599
442872072 619088799 118541378 ...

correct output
143376538

user output
143376538

Test 25

Group: 3

Verdict: ACCEPTED

input
200000 1661
894106972 620084612 931442312 ...

correct output
33089

user output
33089

Test 26

Group: 3

Verdict: ACCEPTED

input
200000 86032
211444153 846442677 297198384 ...

correct output
196001810

user output
196001810

Test 27

Group: 3

Verdict: ACCEPTED

input
200000 28275
28280312 349705372 96535649 84...

correct output
11627219

user output
11627219

Test 28

Group: 3

Verdict: ACCEPTED

input
200000 81473
178022892 112774306 250584651 ...

correct output
162430841

user output
162430841

Test 29

Group: 3

Verdict: ACCEPTED

input
200000 99987
297598052 494409138 182268523 ...

correct output
489497036

user output
489497036

Test 30

Group: 3

Verdict: ACCEPTED

input
200000 99971
316462272 843156468 434342923 ...

correct output
483167476

user output
483167476

Test 31

Group: 3

Verdict: ACCEPTED

input
200000 99964
811543559 465033274 620180191 ...

correct output
481497328

user output
481497328