Task: | Queue |
Sender: | double_deque |
Submission time: | 2017-09-05 18:28:33 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.05 s | details |
#2 | ACCEPTED | 0.03 s | details |
#3 | ACCEPTED | 0.04 s | details |
#4 | ACCEPTED | 0.03 s | details |
#5 | ACCEPTED | 0.04 s | details |
#6 | ACCEPTED | 0.04 s | details |
#7 | ACCEPTED | 0.04 s | details |
#8 | ACCEPTED | 0.05 s | details |
#9 | ACCEPTED | 0.04 s | details |
#10 | ACCEPTED | 0.03 s | details |
#11 | ACCEPTED | 0.05 s | details |
#12 | ACCEPTED | 0.04 s | details |
#13 | ACCEPTED | 0.03 s | details |
#14 | ACCEPTED | 0.05 s | details |
#15 | ACCEPTED | 0.03 s | details |
#16 | ACCEPTED | 0.06 s | details |
#17 | ACCEPTED | 0.04 s | details |
#18 | ACCEPTED | 0.04 s | details |
#19 | ACCEPTED | 0.03 s | details |
#20 | ACCEPTED | 0.05 s | details |
#21 | ACCEPTED | 0.03 s | details |
#22 | ACCEPTED | 0.04 s | details |
#23 | ACCEPTED | 0.04 s | details |
#24 | ACCEPTED | 0.04 s | details |
#25 | ACCEPTED | 0.02 s | details |
#26 | ACCEPTED | 0.06 s | details |
#27 | ACCEPTED | 0.06 s | details |
#28 | ACCEPTED | 0.04 s | details |
#29 | ACCEPTED | 0.05 s | details |
#30 | ACCEPTED | 0.05 s | details |
#31 | ACCEPTED | 0.04 s | details |
#32 | ACCEPTED | 0.04 s | details |
#33 | ACCEPTED | 0.04 s | details |
#34 | ACCEPTED | 0.04 s | details |
#35 | ACCEPTED | 0.05 s | details |
#36 | ACCEPTED | 0.04 s | details |
#37 | ACCEPTED | 0.04 s | details |
#38 | ACCEPTED | 0.05 s | details |
#39 | ACCEPTED | 0.04 s | details |
#40 | ACCEPTED | 0.04 s | details |
#41 | ACCEPTED | 0.06 s | details |
#42 | ACCEPTED | 0.08 s | details |
#43 | ACCEPTED | 0.05 s | details |
#44 | ACCEPTED | 0.05 s | details |
#45 | ACCEPTED | 0.06 s | details |
#46 | ACCEPTED | 0.06 s | details |
#47 | ACCEPTED | 0.04 s | details |
#48 | ACCEPTED | 0.04 s | details |
#49 | ACCEPTED | 0.04 s | details |
#50 | ACCEPTED | 0.06 s | details |
#51 | ACCEPTED | 0.06 s | details |
#52 | ACCEPTED | 0.06 s | details |
#53 | ACCEPTED | 0.05 s | details |
#54 | ACCEPTED | 0.07 s | details |
#55 | ACCEPTED | 0.07 s | details |
#56 | ACCEPTED | 0.05 s | details |
#57 | ACCEPTED | 0.05 s | details |
#58 | ACCEPTED | 0.04 s | details |
#59 | ACCEPTED | 0.07 s | details |
#60 | ACCEPTED | 0.05 s | details |
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, sizestd::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 |