#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long find_maximum(int k, vector<vector<int>> x) {
int n = (int) x.size();
int m = (int) x[0].size();
// choose k items for each color
// choose a total of nk/2 + and nk/2 -
// maximize the sum of + and -
long long ans = 0;
vector<int> negative(n, k);
vector<int> positive(n, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
ans -= x[i][j];
}
}
priority_queue<pair<int, int>> pq;
for (int i = 0; i < n; i++) {
if (negative[i] > 0) {
pq.emplace(x[i][m - positive[i] - 1] + x[i][negative[i] - 1], i);
}
}
for (int rep = 0; rep < n * k / 2 && !pq.empty(); rep++) {
int i = pq.top().second;
ans += pq.top().first;
pq.pop();
negative[i]--;
positive[i]++;
if (negative[i] > 0) {
pq.emplace(x[i][m - positive[i] - 1] + x[i][negative[i] - 1], i);
}
}
vector<pair<int, int>> small;
vector<pair<int, int>> large;
for (int i = 0; i < n; i++) {
for (int j = 0; j < negative[i]; j++) {
small.emplace_back(i, j);
}
for (int j = 0; j < positive[i]; j++) {
large.emplace_back(i, m - j - 1);
}
}
sort(begin(small), end(small));
sort(begin(large), end(large));
vector<vector<pair<int, int>>> rounds(k);
vector<vector<int>> inround(k, vector<int>(n, 0));
for (int i = 0; i < n * k / 2; i++) {
rounds[i % k].emplace_back(small[i]);
inround[i % k][small[i].first] = 1;
}
for (int i = 0, j; i < n * k / 2; i = j + 1) {
for (j = i; j + 1 < n * k / 2 && large[i].first == large[j + 1].first; j++);
vector<pair<int, int>> elems;
for (int e = i; e <= j; e++) {
elems.emplace_back(large[e]);
}
for (int r = 0; r < k; r++) {
if (inround[r][large[i].first] == 0) {
inround[r][large[i].first] = 1;
rounds[r].emplace_back(elems.back());
elems.pop_back();
}
}
}
vector<vector<int>> tickets(n, vector<int>(m, -1));
for (int r = 0; r < k; r++) {
for (int i = 0; i < n; i++) {
tickets[rounds[r][i].first][rounds[r][i].second] = r;
}
}
allocate_tickets(tickets);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
30 ms |
2432 KB |
Output is correct |
6 |
Correct |
744 ms |
51508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
28 ms |
3328 KB |
Output is correct |
6 |
Correct |
741 ms |
69844 KB |
Output is correct |
7 |
Correct |
792 ms |
78276 KB |
Output is correct |
8 |
Correct |
4 ms |
768 KB |
Output is correct |
9 |
Correct |
1 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
8 ms |
1280 KB |
Output is correct |
13 |
Correct |
28 ms |
2812 KB |
Output is correct |
14 |
Correct |
28 ms |
3332 KB |
Output is correct |
15 |
Correct |
830 ms |
84904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
4 ms |
640 KB |
Output is correct |
5 |
Correct |
42 ms |
4424 KB |
Output is correct |
6 |
Correct |
7 ms |
1184 KB |
Output is correct |
7 |
Correct |
8 ms |
1280 KB |
Output is correct |
8 |
Correct |
1151 ms |
95116 KB |
Output is correct |
9 |
Correct |
1093 ms |
88780 KB |
Output is correct |
10 |
Correct |
1025 ms |
89816 KB |
Output is correct |
11 |
Correct |
1117 ms |
95188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
640 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
512 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
4 ms |
672 KB |
Output is correct |
12 |
Correct |
3 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
640 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
512 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
4 ms |
672 KB |
Output is correct |
12 |
Correct |
3 ms |
640 KB |
Output is correct |
13 |
Correct |
30 ms |
2456 KB |
Output is correct |
14 |
Correct |
30 ms |
2432 KB |
Output is correct |
15 |
Correct |
36 ms |
3304 KB |
Output is correct |
16 |
Correct |
44 ms |
4424 KB |
Output is correct |
17 |
Correct |
1 ms |
640 KB |
Output is correct |
18 |
Correct |
3 ms |
512 KB |
Output is correct |
19 |
Correct |
2 ms |
512 KB |
Output is correct |
20 |
Correct |
33 ms |
3580 KB |
Output is correct |
21 |
Correct |
36 ms |
3592 KB |
Output is correct |
22 |
Correct |
35 ms |
4248 KB |
Output is correct |
23 |
Correct |
39 ms |
4168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
1 ms |
256 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
30 ms |
2432 KB |
Output is correct |
12 |
Correct |
744 ms |
51508 KB |
Output is correct |
13 |
Correct |
1 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
256 KB |
Output is correct |
16 |
Correct |
3 ms |
512 KB |
Output is correct |
17 |
Correct |
28 ms |
3328 KB |
Output is correct |
18 |
Correct |
741 ms |
69844 KB |
Output is correct |
19 |
Correct |
792 ms |
78276 KB |
Output is correct |
20 |
Correct |
4 ms |
768 KB |
Output is correct |
21 |
Correct |
1 ms |
256 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
256 KB |
Output is correct |
24 |
Correct |
8 ms |
1280 KB |
Output is correct |
25 |
Correct |
28 ms |
2812 KB |
Output is correct |
26 |
Correct |
28 ms |
3332 KB |
Output is correct |
27 |
Correct |
830 ms |
84904 KB |
Output is correct |
28 |
Correct |
1 ms |
256 KB |
Output is correct |
29 |
Correct |
1 ms |
256 KB |
Output is correct |
30 |
Correct |
1 ms |
256 KB |
Output is correct |
31 |
Correct |
4 ms |
640 KB |
Output is correct |
32 |
Correct |
42 ms |
4424 KB |
Output is correct |
33 |
Correct |
7 ms |
1184 KB |
Output is correct |
34 |
Correct |
8 ms |
1280 KB |
Output is correct |
35 |
Correct |
1151 ms |
95116 KB |
Output is correct |
36 |
Correct |
1093 ms |
88780 KB |
Output is correct |
37 |
Correct |
1025 ms |
89816 KB |
Output is correct |
38 |
Correct |
1117 ms |
95188 KB |
Output is correct |
39 |
Correct |
0 ms |
256 KB |
Output is correct |
40 |
Correct |
3 ms |
512 KB |
Output is correct |
41 |
Correct |
3 ms |
512 KB |
Output is correct |
42 |
Correct |
3 ms |
512 KB |
Output is correct |
43 |
Correct |
3 ms |
512 KB |
Output is correct |
44 |
Correct |
3 ms |
640 KB |
Output is correct |
45 |
Correct |
1 ms |
384 KB |
Output is correct |
46 |
Correct |
1 ms |
384 KB |
Output is correct |
47 |
Correct |
3 ms |
512 KB |
Output is correct |
48 |
Correct |
3 ms |
512 KB |
Output is correct |
49 |
Correct |
4 ms |
672 KB |
Output is correct |
50 |
Correct |
3 ms |
640 KB |
Output is correct |
51 |
Correct |
30 ms |
2456 KB |
Output is correct |
52 |
Correct |
30 ms |
2432 KB |
Output is correct |
53 |
Correct |
36 ms |
3304 KB |
Output is correct |
54 |
Correct |
44 ms |
4424 KB |
Output is correct |
55 |
Correct |
1 ms |
640 KB |
Output is correct |
56 |
Correct |
3 ms |
512 KB |
Output is correct |
57 |
Correct |
2 ms |
512 KB |
Output is correct |
58 |
Correct |
33 ms |
3580 KB |
Output is correct |
59 |
Correct |
36 ms |
3592 KB |
Output is correct |
60 |
Correct |
35 ms |
4248 KB |
Output is correct |
61 |
Correct |
39 ms |
4168 KB |
Output is correct |
62 |
Correct |
87 ms |
6136 KB |
Output is correct |
63 |
Correct |
81 ms |
6136 KB |
Output is correct |
64 |
Correct |
115 ms |
10420 KB |
Output is correct |
65 |
Correct |
405 ms |
30040 KB |
Output is correct |
66 |
Correct |
483 ms |
39924 KB |
Output is correct |
67 |
Correct |
8 ms |
1408 KB |
Output is correct |
68 |
Correct |
7 ms |
1152 KB |
Output is correct |
69 |
Correct |
736 ms |
51736 KB |
Output is correct |
70 |
Correct |
932 ms |
69888 KB |
Output is correct |
71 |
Correct |
1144 ms |
95092 KB |
Output is correct |
72 |
Correct |
907 ms |
90204 KB |
Output is correct |
73 |
Correct |
1048 ms |
89096 KB |
Output is correct |
74 |
Correct |
765 ms |
70076 KB |
Output is correct |
75 |
Correct |
912 ms |
69508 KB |
Output is correct |