CSES - KILO 2017 1/5 - Results
Submission details
Task:Queue
Sender:double_deque
Submission time:2017-09-05 18:28:33 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.03 sdetails
#3ACCEPTED0.04 sdetails
#4ACCEPTED0.03 sdetails
#5ACCEPTED0.04 sdetails
#6ACCEPTED0.04 sdetails
#7ACCEPTED0.04 sdetails
#8ACCEPTED0.05 sdetails
#9ACCEPTED0.04 sdetails
#10ACCEPTED0.03 sdetails
#11ACCEPTED0.05 sdetails
#12ACCEPTED0.04 sdetails
#13ACCEPTED0.03 sdetails
#14ACCEPTED0.05 sdetails
#15ACCEPTED0.03 sdetails
#16ACCEPTED0.06 sdetails
#17ACCEPTED0.04 sdetails
#18ACCEPTED0.04 sdetails
#19ACCEPTED0.03 sdetails
#20ACCEPTED0.05 sdetails
#21ACCEPTED0.03 sdetails
#22ACCEPTED0.04 sdetails
#23ACCEPTED0.04 sdetails
#24ACCEPTED0.04 sdetails
#25ACCEPTED0.02 sdetails
#26ACCEPTED0.06 sdetails
#27ACCEPTED0.06 sdetails
#28ACCEPTED0.04 sdetails
#29ACCEPTED0.05 sdetails
#30ACCEPTED0.05 sdetails
#31ACCEPTED0.04 sdetails
#32ACCEPTED0.04 sdetails
#33ACCEPTED0.04 sdetails
#34ACCEPTED0.04 sdetails
#35ACCEPTED0.05 sdetails
#36ACCEPTED0.04 sdetails
#37ACCEPTED0.04 sdetails
#38ACCEPTED0.05 sdetails
#39ACCEPTED0.04 sdetails
#40ACCEPTED0.04 sdetails
#41ACCEPTED0.06 sdetails
#42ACCEPTED0.08 sdetails
#43ACCEPTED0.05 sdetails
#44ACCEPTED0.05 sdetails
#45ACCEPTED0.06 sdetails
#46ACCEPTED0.06 sdetails
#47ACCEPTED0.04 sdetails
#48ACCEPTED0.04 sdetails
#49ACCEPTED0.04 sdetails
#50ACCEPTED0.06 sdetails
#51ACCEPTED0.06 sdetails
#52ACCEPTED0.06 sdetails
#53ACCEPTED0.05 sdetails
#54ACCEPTED0.07 sdetails
#55ACCEPTED0.07 sdetails
#56ACCEPTED0.05 sdetails
#57ACCEPTED0.05 sdetails
#58ACCEPTED0.04 sdetails
#59ACCEPTED0.07 sdetails
#60ACCEPTED0.05 sdetails

Code

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
const int M = 2000;
const int N = 1e5;
const long long inf = 1e18;
std::vector<int> members [M];
int fit[M+1]; // How many people from groups 1..i can be fitted to one bus?
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
int n, m, k;
std::cin >> n >> m >> k;
// Time, size
std::vector<std::pair<int, int>> groups;
for (int i = 0; i < n; ++i) {
int a;
std::cin >> a;
members[a-1].push_back(i+1);
}
for (int i = 0; i < m; ++i) {
if (! members[i].empty()) {
groups.push_back({members[i][members[i].size()-1], members[i].size()});
}
}
std::sort(groups.begin(), groups.end());
/*
for (int i = 0; i < groups.size(); ++i) {
std::cout << groups[i].first << ' ' << groups[i].second << '\n';
}
*/
fit[0] = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 0; j < i; ++j) {
if (fit[j] + groups[i-1].second <= k) {
fit[i] = std::max(fit[i], fit[j] + groups[i-1].second);
}
}
//std::cout << fit[i] << '\n';
}
long long cost = inf;
for (int i = groups.size()-2; i >= 0; --i) {
int first = fit[i+1];
int second = n - fit[i+1];
if (second <= k) {
cost = std::min(cost, first * (long long) groups[i].first + second * (long long) n);
}
}
if (n <= k) {
cost = std::min(cost, n * (long long)n);
}
if (cost == inf) {
std::cout << "-1\n";
} else {
std::cout << cost << '\n';
}
}

Test details

Test 1

Verdict: ACCEPTED

input
4 3 2
1 1 1 1

correct output
-1

user output
-1

Test 2

Verdict: ACCEPTED

input
6 6 5
2 1 2 2 2 1

correct output
32

user output
32

Test 3

Verdict: ACCEPTED

input
3 2 3
1 1 1

correct output
9

user output
9

Test 4

Verdict: ACCEPTED

input
3 1 3
1 1 1

correct output
9

user output
9

Test 5

Verdict: ACCEPTED

input
2 2 2
1 2

correct output
3

user output
3

Test 6

Verdict: ACCEPTED

input
10 9 5
1 1 1 1 2 9 9 9 9 9

correct output
75

user output
75

Test 7

Verdict: ACCEPTED

input
8 2 7
1 1 1 1 1 2 2 2

correct output
49

user output
49

Test 8

Verdict: ACCEPTED

input
10 6 7
1 1 1 1 1 1 6 6 6 6

correct output
76

user output
76

Test 9

Verdict: ACCEPTED

input
6 3 4
3 3 3 3 2 3

correct output
-1

user output
-1

Test 10

Verdict: ACCEPTED

input
3 3 2
1 1 1

correct output
-1

user output
-1

Test 11

Verdict: ACCEPTED

input
43893 9 34336
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1498448497

user output
1498448497

Test 12

Verdict: ACCEPTED

input
17481 8 11137
3 2 5 2 6 1 8 6 1 6 1 7 5 1 1 ...

correct output
305552418

user output
305552418

Test 13

Verdict: ACCEPTED

input
28826 9 20049
1 1 3 1 1 3 1 2 1 1 2 1 2 1 1 ...

correct output
830887525

user output
830887525

Test 14

Verdict: ACCEPTED

input
39533 8 27095
1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 ...

correct output
-1

user output
-1

Test 15

Verdict: ACCEPTED

input
71270 6 53774
4 4 1 2 6 1 1 6 4 3 1 2 5 5 5 ...

correct output
-1

user output
-1

Test 16

Verdict: ACCEPTED

input
41203 8 24337
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1320922405

user output
1320922405

Test 17

Verdict: ACCEPTED

input
47138 7 40668
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1671316774

user output
1671316774

Test 18

Verdict: ACCEPTED

input
7651 7 4893
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
43907177

user output
43907177

Test 19

Verdict: ACCEPTED

input
34482 4 23135
4 1 2 2 2 3 3 2 2 1 1 3 4 1 1 ...

correct output
1188973626

user output
1188973626

Test 20

Verdict: ACCEPTED

input
55403 4 28518
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
-1

user output
-1

Test 21

Verdict: ACCEPTED

input
32814 412 28236
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
963667791

user output
963667791

Test 22

Verdict: ACCEPTED

input
26243 357 18652
181 4 163 158 15 132 2 75 127 ...

correct output
685896169

user output
685896169

Test 23

Verdict: ACCEPTED

input
41483 1432 33362
25 33 220 218 134 4 129 165 26...

correct output
1712939621

user output
1712939621

Test 24

Verdict: ACCEPTED

input
47007 1501 42152
108 21 18 106 68 67 18 39 46 2...

correct output
2206183867

user output
2206183867

Test 25

Verdict: ACCEPTED

input
83160 244 71321
173 221 90 62 126 105 108 183 ...

correct output
6908701076

user output
6908701076

Test 26

Verdict: ACCEPTED

input
75458 761 55759
6 4 8 4 9 32 15 42 21 4 9 7 6 ...

correct output
4361407820

user output
4361407820

Test 27

Verdict: ACCEPTED

input
35163 867 24205
1 1 4 4 1 2 2 1 1 1 1 1 1 2 6 ...

correct output
927749839

user output
927749839

Test 28

Verdict: ACCEPTED

input
20899 1205 20082
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
327576151

user output
327576151

Test 29

Verdict: ACCEPTED

input
52868 1263 34676
874 8 846 137 306 1005 349 632...

correct output
2770414204

user output
2770414204

Test 30

Verdict: ACCEPTED

input
6634 1439 6197
1 1 1 1 1 1 1 1 1 1 1 1 1 1 12...

correct output
38501796

user output
38501796

Test 31

Verdict: ACCEPTED

input
984 524 694
1 1 1 1 1 1 103 447 47 46 302 ...

correct output
826296

user output
826296

Test 32

Verdict: ACCEPTED

input
351 263 185
17 123 178 84 19 41 70 70 174 ...

correct output
107763

user output
107763

Test 33

Verdict: ACCEPTED

input
2607 363 1692
105 111 52 81 33 41 82 88 43 7...

correct output
6677793

user output
6677793

Test 34

Verdict: ACCEPTED

input
1896 65 1326
1 11 4 1 2 2 4 4 1 1 5 3 1 3 2...

correct output
3589614

user output
3589614

Test 35

Verdict: ACCEPTED

input
1435 19 770
2 6 11 2 18 19 19 12 17 12 12 ...

correct output
-1

user output
-1

Test 36

Verdict: ACCEPTED

input
2014 961 1228
18 41 4 6 31 8 9 6 47 55 1 9 4...

correct output
3052817

user output
3052817

Test 37

Verdict: ACCEPTED

input
2510 863 1932
1 9 1 1 3 3 1 1 2 1 2 6 6 1 2 ...

correct output
4725076

user output
4725076

Test 38

Verdict: ACCEPTED

input
2279 800 2005
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
3895381

user output
3895381

Test 39

Verdict: ACCEPTED

input
3044 1282 2850
231 1226 166 709 882 1231 1041...

correct output
8304793

user output
8304793

Test 40

Verdict: ACCEPTED

input
1560 1559 1482
1 1 1 1 579 629 68 256 1543 10...

correct output
2036808

user output
2036808

Test 41

Verdict: ACCEPTED

input
100000 2000 78605
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
8957965216

user output
8957965216

Test 42

Verdict: ACCEPTED

input
100000 2000 94147
325 343 6 1583 1423 143 710 43...

correct output
9938031990

user output
9938031990

Test 43

Verdict: ACCEPTED

input
100000 2000 65865
458 353 288 679 148 706 164 58...

correct output
9972374542

user output
9972374542

Test 44

Verdict: ACCEPTED

input
100000 2000 53937
106 33 37 110 24 8 10 25 171 7...

correct output
9993018364

user output
9993018364

Test 45

Verdict: ACCEPTED

input
100000 2000 89553
529 222 626 1397 1697 910 1394...

correct output
9764828240

user output
9764828240

Test 46

Verdict: ACCEPTED

input
100000 2000 83767
25 17 88 123 18 34 4 111 1 7 1...

correct output
7631468065

user output
7631468065

Test 47

Verdict: ACCEPTED

input
100000 2000 86917
3 7 1 1 6 1 11 2 2 1 9 2 10 1 ...

correct output
7504708607

user output
7504708607

Test 48

Verdict: ACCEPTED

input
100000 2000 93483
1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 ...

correct output
7500000000

user output
7500000000

Test 49

Verdict: ACCEPTED

input
100000 2000 54022
491 448 31 519 1204 1123 1050 ...

correct output
9926723265

user output
9926723265

Test 50

Verdict: ACCEPTED

input
100000 2000 76351
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
8965046209

user output
8965046209

Test 51

Verdict: ACCEPTED

input
100000 2000 88758
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
8953639248

user output
8953639248

Test 52

Verdict: ACCEPTED

input
100000 2000 76483
813 438 96 1605 334 27 1280 76...

correct output
9940504263

user output
9940504263

Test 53

Verdict: ACCEPTED

input
100000 2000 66902
8 663 43 227 365 376 315 61 49...

correct output
9972854726

user output
9972854726

Test 54

Verdict: ACCEPTED

input
100000 2000 78996
126 6 55 50 171 68 98 53 164 1...

correct output
9990578620

user output
9990578620

Test 55

Verdict: ACCEPTED

input
100000 2000 57456
552 543 1137 875 1129 1105 116...

correct output
9995460868

user output
9995460868

Test 56

Verdict: ACCEPTED

input
100000 2000 94581
66 8 30 11 5 10 20 28 7 1 207 ...

correct output
7623200605

user output
7623200605

Test 57

Verdict: ACCEPTED

input
100000 2000 99344
2 2 15 10 1 3 15 4 1 3 3 8 2 1...

correct output
7503153298

user output
7503153298

Test 58

Verdict: ACCEPTED

input
100000 2000 52595
1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 ...

correct output
7500000009

user output
7500000009

Test 59

Verdict: ACCEPTED

input
100000 2000 90834
478 937 1119 766 1425 368 1620...

correct output
9924835834

user output
9924835834

Test 60

Verdict: ACCEPTED

input
100000 2000 94089
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
8950028575

user output
8950028575