CSES - Datatähti Open 2021

Submission details
Task:	Programmers
Sender:	MAKMED1337
Submission time:	2021-01-30 20:28:58 +0200
Language:	C++ (C++11)
Status:	READY
Result:	34

Feedback
group	verdict	score
#1	ACCEPTED	34
#2	RUNTIME ERROR	0
#3	RUNTIME ERROR	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 2, 3	details
#2	ACCEPTED	0.01 s	1, 2, 3	details
#3	ACCEPTED	0.01 s	1, 2, 3	details
#4	ACCEPTED	0.01 s	1, 2, 3	details
#5	ACCEPTED	0.01 s	1, 2, 3	details
#6	ACCEPTED	0.01 s	1, 2, 3	details
#7	ACCEPTED	0.01 s	1, 2, 3	details
#8	ACCEPTED	0.02 s	1, 2, 3	details
#9	ACCEPTED	0.03 s	1, 2, 3	details
#10	ACCEPTED	0.03 s	1, 2, 3	details
#11	ACCEPTED	0.01 s	1, 2, 3	details
#12	ACCEPTED	0.01 s	1, 3	details
#13	ACCEPTED	0.01 s	1, 3	details
#14	ACCEPTED	0.02 s	1, 3	details
#15	ACCEPTED	0.01 s	1, 3	details
#16	ACCEPTED	0.03 s	1, 3	details
#17	RUNTIME ERROR	0.43 s	2, 3	details
#18	RUNTIME ERROR	0.75 s	2, 3	details
#19	RUNTIME ERROR	0.75 s	2, 3	details
#20	RUNTIME ERROR	0.76 s	2, 3	details
#21	RUNTIME ERROR	0.76 s	2, 3	details
#22	RUNTIME ERROR	0.76 s	2, 3	details
#23	RUNTIME ERROR	0.74 s	2, 3	details
#24	RUNTIME ERROR	0.76 s	3	details
#25	RUNTIME ERROR	0.76 s	3	details
#26	RUNTIME ERROR	0.78 s	3	details
#27	RUNTIME ERROR	0.76 s	3	details
#28	RUNTIME ERROR	0.77 s	3	details
#29	RUNTIME ERROR	0.76 s	3	details
#30	RUNTIME ERROR	0.77 s	3	details
#31	RUNTIME ERROR	0.78 s	3	details

Code

#include <bits/stdc++.h>
#include <climits>

using namespace std;

template<class T>
using V = vector<T>;
template<class T>
using VV = V<V<T>>;

using ld = long double;
#define ll long long
using ull = unsigned ll;
using PLL = pair<ll, ll>;
using VLL = V<ll>;
using VB = V<bool>;
using VVB = VV<bool>;
using VVLL = VV<ll>;
using Gr = VVLL;
using MLL = map<ll, ll>;
#define UMLL unordered_map<ll, ll, custom_hash>

//using int128 = __int128;
//using double128 = __float128;

#define fast ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); cerr.tie(nullptr);

#define INF 100000000000000
#define MINF LONG_MIN

#define R &
#define CR const R

#define FORI(i, a, b) for(ll i = a, max##i = b; i < max##i; ++i)
#define FOR(i, n) FORI(i, 0, n)
#define RFORI(i, a, b) for(ll i = a, min##i = b; i >= min##i; --i)
#define RFOR(i, n) RFORI(i, n, 0)
#define FORA(i, a) for(auto i : a)
#define FORAR(i, a) for(auto R i : a)
#define FORACR(i, a) for(auto CR i : a)
#define ALL(obj) begin(obj), end(obj)
#define Count(q) while(q--)
#define OK cerr << "OK\n";

#define mp make_pair
#define pb push_back

//#define DEBUG

template<class T>
T sqr(T x)
{
    return x * x;
}

void YES(bool g, ostream R os, bool upper = true)
{
    if(g)
        if(upper)
            os << "YES";
        else
            os << "Yes";
    else
        if(upper)
            os << "NO";
        else
            os << "No";

    os << "\n";
}

template<class T>
void show(T CR t, ostream R os = cerr)
{
    FORACR(i, t)
        os << i << " ";
    os << "\n";
}

template<class T>
void show2d(T CR t, ostream R os = cerr)
{
    FORACR(i, t)
        show(i, os);
    os << "\n";
}

constexpr ll MOD = 1e9 + 7;
constexpr ll len = 40320 + 1;

constexpr ld PI = atanl(1.0L) * 4;

struct custom_hash
{
    static uint64_t splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator() (uint64_t x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

//arr
void init() {}

void solve(istream R is, ostream R os)
{
    ll n, k;
    is >> n >> k;

    VLL a(n);
    FORAR(i, a)
        is >> i;

    sort(ALL(a));
    show(a);

    VVLL dp(n, VLL(k + 1, INF));
    dp[0][0] = 0;
    dp[1][0] = 0;
    dp[1][1] = a[1] - a[0];

    FORI(i, 2, n)
    {
        FOR(j, k + 1)
            dp[i][j] = dp[i - 1][j];

        FOR(j, k)
            dp[i][j + 1] = min(dp[i][j + 1], a[i] - a[i - 1] + dp[i - 2][j]);
    }

    //cerr << "\n\n";
    //show2d(dp);

    os << dp[n - 1][k] << "\n";
}

void tester(istream R is, ostream R os)
{
    fast
    init();
    ll q = 1;
    //is >> q;
    os << setprecision(999);

    Count(q)
        solve(is, os);
}

int main()
{
    //ifstream in("input.txt");
    //ofstream out("output.txt");

    tester(cin, cout);
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
`8 3 3 1 2 7 9 3 4 7` view save

correct output
`1` view save

user output
`1` view save

Error:

1 2 3 3 4 7 7 9

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2 1 2 13` view save

correct output
`11` view save

user output
`11` view save

Error:

2 13

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`20 10 16 20 6 15 19 12 11 17 20 6 15...` view save

correct output
`6` view save

user output
`6` view save

Error:

6 6 7 9 11 11 11 12 12 12 15 15 15 15 15 16 17 19 20 20

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`14 5 11 3 8 3 14 8 10 13 11 10 17 1...` view save

correct output
`0` view save

user output
`0` view save

Error:

3 3 3 8 8 10 10 11 11 12 13 14 17 17

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
`0` view save

user output
`0` view save

Error:

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

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
`10 3 10 19 16 15 12 5 14 8 3 15` view save

correct output
`4` view save

user output
`4` view save

Error:

3 5 8 10 12 14 15 15 16 19

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
`213` view save

user output
`213` view save

Error:

3 4 6 9 10 15 16 17 21 22 27 28 29 29 43 44 46 46 63 63 70 74 75 90 97 101 102 108 118 129...

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
`0` view save

user output
`0` view save

Error:

1 1 2 3 4 4 5 5 5 5 6 6 7 8 9 11 12 12 13 13 13 14 14 15 15 16 16 18 18 18 18 18 19 19 19...

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
`276` view save

user output
`276` view save

Error:

1 2 2 2 3 4 4 4 4 4 4 5 5 6 6 6 6 6 7 7 7 8 8 9 9 9 10 10 11 12 14 14 14 14 15 15 15 15 17...

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
`517` view save

user output
`517` view save

Error:

1 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 7 9 10 10 10 11 12 13 15 16 16 19 19 20 20 20 21 21 22...

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
`0` view save

user output
`0` view save

Error:

1 1 2 2 2 4 4 4 4 5 6 6 7 7 7 7 7 7 7 9 9 9 9 9 10 11 11 11 11 11 13 14 14 15 15 17 17 17...

Test 12

Group: 1, 3

Verdict: ACCEPTED

input
`1464 320 846762124 954854396 12767390 7...` view save

correct output
`35809369` view save

user output
`35809369` view save

Error:

729941 2182947 3249752 4444498 5825151 6483997 8276666 8832459 10646312 10669155 10702140...

Test 13

Group: 1, 3

Verdict: ACCEPTED

input
`2000 231 801945178 924940258 369188694 ...` view save

correct output
`7831421` view save

user output
`7831421` view save

Error:

1662213 2157290 2242927 2348140 2424543 2824426 3133117 3136796 3137737 3524940 3849355 43...

Test 14

Group: 1, 3

Verdict: ACCEPTED

input
`2000 461 464790475 932031556 838378103 ...` view save

correct output
`37272564` view save

user output
`37272564` view save

Error:

109741 172937 316249 888123 1080811 1098179 1486955 1604180 1921862 2763003 2794522 362135...

Test 15

Group: 1, 3

Verdict: ACCEPTED

input
`2000 100 484046702 267135814 995006323 ...` view save

correct output
`1268400` view save

user output
`1268400` view save

Error:

237534 476236 718459 851444 1198028 1898518 2584877 2882841 3638157 3695785 4089790 438188...

Test 16

Group: 1, 3

Verdict: ACCEPTED

input
`2000 996 98352148 438929491 242618159 1...` view save

correct output
`445965905` view save

user output
`445965905` view save

Error:

956313 2022285 2775367 2784387 3712801 4817536 4992304 5270190 6687493 6697565 7207841 808...

Test 17

Group: 2, 3

Verdict: RUNTIME ERROR

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

correct output
`0` view save

user output
(empty)

Error:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

Test 18

Group: 2, 3

Verdict: RUNTIME ERROR

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

correct output
`0` view save

user output
(empty)

Error:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

Test 19

Group: 2, 3

Verdict: RUNTIME ERROR

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

correct output
`0` view save

user output
(empty)

Error:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

Test 20

Group: 2, 3

Verdict: RUNTIME ERROR

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

correct output
`322` view save

user output
(empty)

Error:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

Test 21

Group: 2, 3

Verdict: RUNTIME ERROR

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

correct output
`245` view save

user output
(empty)

Error:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

Test 22

Group: 2, 3

Verdict: RUNTIME ERROR

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

correct output
`290` view save

user output
(empty)

Error:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

Test 23

Group: 2, 3

Verdict: RUNTIME ERROR

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

correct output
`252` view save

user output
(empty)

Error:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

Test 24

Group: 3

Verdict: RUNTIME ERROR

input
`195426 76599 442872072 619088799 118541378 ...` view save

correct output
`143376538` view save

user output
(empty)

Error:

8599 17173 17263 18609 28458 31442 38732 39986 40467 43002 48663 59304 63560 73285 74171 7...

Test 25

Group: 3

Verdict: RUNTIME ERROR

input
`200000 1661 894106972 620084612 931442312 ...` view save

correct output
`33089` view save

user output
(empty)

Error:

1334 1572 4569 8051 9747 13002 14186 15276 15304 18705 29646 30369 35408 40287 45898 46678...

Test 26

Group: 3

Verdict: RUNTIME ERROR

input
`200000 86032 211444153 846442677 297198384 ...` view save

correct output
`196001810` view save

user output
(empty)

Error:

4430 4666 6150 14869 18481 23043 26707 38838 58112 70916 71027 74063 80403 82836 87802 895...

Test 27

Group: 3

Verdict: RUNTIME ERROR

input
`200000 28275 28280312 349705372 96535649 84...` view save

correct output
`11627219` view save

user output
(empty)

Error:

3772 10645 12298 24710 24975 25733 26246 43471 46211 51677 54250 58562 59157 60714 63678 6...

Test 28

Group: 3

Verdict: RUNTIME ERROR

input
`200000 81473 178022892 112774306 250584651 ...` view save

correct output
`162430841` view save

user output
(empty)

Error:

847 10466 12559 15297 17446 18275 22130 43852 44424 45549 46278 53760 61677 63521 66214 76...

Test 29

Group: 3

Verdict: RUNTIME ERROR

input
`200000 99987 297598052 494409138 182268523 ...` view save

correct output
`489497036` view save

user output
(empty)

Error:

6245 18418 23101 32244 34642 38131 40746 41887 43602 53474 58309 68766 71021 74421 76556 7...

Test 30

Group: 3

Verdict: RUNTIME ERROR

input
`200000 99971 316462272 843156468 434342923 ...` view save

correct output
`483167476` view save

user output
(empty)

Error:

6082 10614 11604 11698 18769 22465 26511 26527 33192 33208 36563 55132 56926 57747 65921 6...

Test 31

Group: 3

Verdict: RUNTIME ERROR

input
`200000 99964 811543559 465033274 620180191 ...` view save

correct output
`481497328` view save

user output
(empty)

Error:

1699 3051 8056 10671 18590 19433 20963 24716 28899 38275 54821 55285 56722 57282 58126 682...

Datatähti Open 2021

Programmers

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Tasks

Submissions (MAKMED1337)