CSES - Datatähti Open 2021 - Results
Submission details
Task:Programmers
Sender:f1x9d
Submission time:2021-01-30 16:50:35 +0200
Language:C++17
Status:READY
Result:55
Feedback
groupverdictscore
#1ACCEPTED34
#2ACCEPTED21
#30
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.02 s1, 2, 3details
#9ACCEPTED0.03 s1, 2, 3details
#10ACCEPTED0.03 s1, 2, 3details
#11ACCEPTED0.01 s1, 2, 3details
#12ACCEPTED0.02 s1, 3details
#13ACCEPTED0.02 s1, 3details
#14ACCEPTED0.02 s1, 3details
#15ACCEPTED0.01 s1, 3details
#16ACCEPTED0.04 s1, 3details
#17ACCEPTED0.02 s2, 3details
#18ACCEPTED0.04 s2, 3details
#19ACCEPTED0.04 s2, 3details
#20ACCEPTED0.08 s2, 3details
#21ACCEPTED0.08 s2, 3details
#22ACCEPTED0.08 s2, 3details
#23ACCEPTED0.08 s2, 3details
#240.71 s3details
#250.30 s3details
#260.75 s3details
#270.51 s3details
#280.75 s3details
#290.83 s3details
#300.83 s3details
#310.83 s3details

Compiler report

input/code.cpp: In function 'void solve()':
input/code.cpp:56:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); i ++) {
                     ~~^~~~~~~~~~
input/code.cpp: At global scope:
input/code.cpp:83:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

Code

#include <bits/stdc++.h>
//#pragma GCC optimize "O3"
///if ((double) ((double)(clock() - cl)/(double)CLOCKS_PER_SEC)>1.85) { break;}
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define double long double
#define ft first
#define sc second
#define pb push_back
#define e '\n'
#define booost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
#define all(x) (x).begin(),(x).end()
#define file(x) freopen(string(string((x)) + ".in").c_str(), "r", stdin); freopen(string(string((x)) + ".out").c_str(), "w", stdout);
#define GG cout << " OPA " << '\n';

using namespace std;
using namespace __gnu_pbds;

typedef pair <int, int> pi;
typedef tree <pi, null_type, less<pi>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 8e3 + 5;
const int K = 10;
const int KK = 20;
const int INF = 1e15;
const double d_INF = 2000000000.0;
const double EPS = 1e-17;
const int MOD = 1e9 + 7;
const int LOG = 30;

int dp[N][N][2];
int a[N];
int b[N];

void solve() {
    int n, k;
    cin >> n >> k;
    map <int, int> mp;
    for (int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        mp[x] ++;
    }
    vector <int> v;
    for (auto it : mp) {
        if (it.sc >= 4) {
            if (it.sc % 2) v.pb(it.ft);
            k -= (it.sc - 2) / 2;
            v.pb(it.ft);
            v.pb(it.ft);
        }
        else for (int i = 0; i < it.sc; i ++) v.pb(it.ft);
    }
    sort (all(v));
    for (int i = 0; i < v.size(); i ++) {
        a[i + 1] = v[i];
    }
    n = v.size();
    if (k <= 0) {cout << 0; return;}
    for (int i = 0; i <= n; i ++) {
        for (int j = 0; j <= k; j ++) {
            for (int z = 0; z < 2; z ++) {
                dp[i][j][z] = INF;
            }
        }
    }
    sort (a + 1, a + n + 1);
    dp[0][0][0] = 0;
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= k; j ++) {
            if (j != k && i > 1) dp[i][j + 1][1] = min(dp[i][j + 1][1], min(dp[i - 2][j][1], dp[i - 2][j][0]) + (a[i] - a[i - 1]));
            dp[i][j][0] = min(dp[i][j][0], min(dp[i - 1][j][1], dp[i - 1][j][0]));
        }
    }
    int ans = INF;
    for (int i = 1; i <= n; i ++) {
        ans = min(ans, dp[i][k][0]);
        ans = min(ans, dp[i][k][1]);
    }
    cout << ans;
}
main () {
    int test = 1;
    booost;
//    cin >> test;
    while (test --) {
        solve();
    }
}

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:

input
195426 76599
442872072 619088799 118541378 ...

correct output
143376538

user output
(empty)

Test 25

Group: 3

Verdict:

input
200000 1661
894106972 620084612 931442312 ...

correct output
33089

user output
(empty)

Test 26

Group: 3

Verdict:

input
200000 86032
211444153 846442677 297198384 ...

correct output
196001810

user output
(empty)

Test 27

Group: 3

Verdict:

input
200000 28275
28280312 349705372 96535649 84...

correct output
11627219

user output
(empty)

Test 28

Group: 3

Verdict:

input
200000 81473
178022892 112774306 250584651 ...

correct output
162430841

user output
(empty)

Test 29

Group: 3

Verdict:

input
200000 99987
297598052 494409138 182268523 ...

correct output
489497036

user output
(empty)

Test 30

Group: 3

Verdict:

input
200000 99971
316462272 843156468 434342923 ...

correct output
483167476

user output
(empty)

Test 31

Group: 3

Verdict:

input
200000 99964
811543559 465033274 620180191 ...

correct output
481497328

user output
(empty)